Python | Simple Binary Search | O(n log n), O(n) | Beats 100%
CodeComplexity
Time complexity: O(n log n). Binary search is n log(n), 0 to n houses binary search that each call isValidCap() with n time. posCaps is made with
# Code
```python3 []
class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        def isValidCap(cap):
            robbed, canRob = 0, True
            for house in nums:
                if not canRob:
                    canRob = True # can't rob house, need to skip and can now rob next
                elif house <= cap:
                    robbed += 1 # can rob house and house less than cap, so rob
                    canRob = False # can't rob next house
            return robbed >= k # if can rob at least k houses, then cap is valid

        posCaps = list(sorted(set(nums))) # sorted list of all possible capacities
        left, right = 0, len(posCaps) - 1 # indices of posCaps

        while left < right: # binary search for lowest posCap[i]
            mid = (left + right) // 2

            if isValidCap(posCaps[mid]):
                right = mid # valid capacity, move right down to look for smaller
            else:
                left = mid + 1 # current capacity can't make k groups, move left up

        # left = right, posCap[left or right] = min capacity that can make k groups
        # posCaps[left - 1] is first capacity that is too small
        return posCaps[left] 
```

# Complexity
- Time complexity: $$O(n\ log\ n)$$. Binary search is n log(n), 0 to n houses binary search that each call isValidCap() with n time. posCaps is made with set(), sorted(), and list() which have times of n, n log(n), and n, respectively. Overall time is n log(n).
- Space complexity: $$O(n)$$. posCaps can store all elements of nums, so has size n. Other variables are constant space, so n overall.

# Performance

![Screenshot (15).png](https://assets.leetcode.com/users/images/c5ebb3fa-2efd-46dc-90f3-9165f5ef972c_1741999243.2159603.png)

['Binary Search', 'Python3']