Easy to Understand || simple code || Binary Search || Min-Max approach || c++ || python
House Robber IVIntuitionWe need to determine the minimum "capability" (i.e. threshold) such that the robber can choose at least k houses without ever choosing t
# House Robber IV

## Intuition
We need to determine the minimum "capability" (i.e. threshold) such that the robber can choose at least **k** houses without ever choosing two consecutive houses. A house can only be robbed if its value is at most the current threshold. If we can rob **k** houses with a given threshold, we might be able to lower it further. This naturally leads us to apply a binary search over the range of possible house values.

## Approach
1. **Binary Search Range:**  
   - The lowest capability can be the minimum value in `nums`, and the highest can be the maximum value.
2. **Greedy Check:**  
   - For each candidate threshold `mid`, we traverse the houses and greedily decide to rob whenever the house value is ≤ `mid`, skipping the next house to avoid adjacency.
3. **Adjusting Search:**  
   - If with `mid` as capability we can rob at least **k** houses, we try to lower the threshold. Otherwise, we increase it.

## Complexity
- **Time Complexity:** O(n log M)  
  Where **n** is the number of houses and **M** is the range between the maximum and minimum house values. We perform a binary search (O(log M)) and for each search step, we check the array in O(n).

- **Space Complexity:** O(1)  
  We use only a few extra variables for the binary search and greedy check.
## Example Walkthrough

```cpp []
// Example demonstrating how the solution checks feasibility:

// Input:
nums = [2, 3, 5, 9, 6];
int k = 2;

// Binary Search Range:
int low = 2;
int high = 9;

// First check with mid = (low + high) / 2 = 5
// - Rob house 1 (value = 2 ≤ 5), skip house 2
// - Rob house 3 (value = 5 ≤ 5), skip house 4
// => Total robbed = 2, which meets k
// Since it's feasible, we try to lower the threshold.
```


# Code
```cpp []
class Solution {
public:
    bool solve(int res,vector<int>& nums, int k){
        int cnt=0;
        for(int i=0;i<nums.size();i++){
            if(res>=nums[i]){
                cnt++;
                i++;
            }
        }
        return cnt>=k;
    }
    int minCapability(vector<int>& nums, int k) {
        int n=nums.size();
        int low=*min_element(nums.begin(),nums.end());
        int high=*max_element(nums.begin(),nums.end());

        int ans=low;
        
        while(low<=high){
            int mid=(low+high)/2;
            if(solve(mid,nums,k)){
                ans=mid;
                high=mid-1;
            }else{
                low=mid+1;
            }
        }
        return ans;
    }
};
```
```python []
class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        def can_rob(res, houses, k):
            count = 0
            i = 0
            while i < len(houses):
                if houses[i] <= res:
                    count += 1
                    i += 2
                else:
                    i += 1
                if count >= k:
                    return True
            return False

        low, high = min(nums), max(nums)
        ans = high

        while low <= high:
            mid = (low + high) // 2
            if can_rob(mid, nums, k):
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
        return ans

```
['Array', 'Binary Search', 'Greedy', 'Python', 'C++']