Binary search to the rescue again!
IntuitionWe can binary serach on the capability becauseif capability x is possible, capabilities greater than x are also possibleApproachTo check if capability
# Intuition
 We can binary serach on the capability because

if capability $$x$$ is possible, capabilities greater than $$x$$ are also possible

    An important tip from the editorial: "Problems that require maximizing the minimum or minimizing the maximum often suggest a binary search approach."

# Approach
To check if capability $x$ is possible in $O(n)$, we can greedily choose to count current index if its value is less than $x$ and skip next index.

# Complexity
- Time complexity:
$$O(n \log m)$$ where $n$ is the size of $\text{nums}$ array and $m$ is the maximum value in the array

- Space complexity:
$O(1)$

# Code
```cpp []
class Solution {
public:

    /**
    We can binary serach on the capability

    If capability x is possible capabilities greater than x are also possible

     Problems that require maximizing the minimum or minimizing the maximum often suggest a binary search approach.
     */

    bool isPossible(vector<int> &nums, int x, int k) {
        // check if capability x is possible in choosing atleast k houses
        // choose k houses greedily starting from first index
        
        int chosenCount = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] <= x) {
                chosenCount++;
                i++;
            }
        }
        return chosenCount >= k;
    }

    int minCapability(vector<int>& nums, int k) {
        if (k == 1) { // can return min element
            return *min_element(nums.begin(), nums.end());
        }
        int minX = *min_element(nums.begin(), nums.end());
        int maxX = *max_element(nums.begin(), nums.end());

        int start = minX, end = maxX;
        int ans = maxX;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (isPossible(nums, mid, k)) {
                ans = mid;
                end = mid - 1; // look for lower x
            } else {
                start = mid + 1;
            }
        }
        return ans;
    }
};
```
['Array', 'Binary Search', 'C++']