🏠 House Robber IV | Binary Search + Greedy | O(n log max(nums)) Complexity 🔍💰 
IntuitionWe need to find the minimum capability such that we can rob at least k houses without robbing adjacent houses.A brute-force approach would involve chec
# Intuition  
We need to find the **minimum capability** such that we can rob at least `k` houses **without robbing adjacent houses**.  

A brute-force approach would involve checking all subsets, which is inefficient. Instead, we can use **binary search** on the capability value (the maximum amount a robbed house can contain) to optimize our solution.  

---

# Approach  

### 1. **Define the Search Space:**  
   - The **minimum** possible capability is `l = 0` (if we don't rob any house).  
   - The **maximum** possible capability is `h = max(nums)`, since we cannot rob a house with a value greater than `max(nums)`.  

### 2. **Binary Search on Capability (`mid`):**  
   - We check if it's **possible** to rob at least `k` houses while ensuring that the maximum robbed house value does not exceed `mid`.  
   - If it's **possible**, we try lowering `mid` (`h = mid`) to minimize the capability.  
   - If it's **not possible**, we increase `mid` (`l = mid`).  

### 3. **Validation Function (`valid()`):**  
   - Traverse the `nums` array and greedily select houses to rob, **skipping adjacent ones**.  
   - If the house value is `≤ mid`, rob it and move `2` steps forward.  
   - Keep track of the number of robbed houses (`res`).  
   - If `res >= k`, return `true`, otherwise `false`.  

### 4. **Binary Search Termination:**  
   - When `l` and `h` converge, `h` is the minimum capability required to rob at least `k` houses.  

---

# Complexity  

- **Time Complexity:**  
  - **Binary search range:** `O(log max(nums))` (searching within `[0, max(nums)]`).  
  - **Validation check (`valid()`)** iterates through `nums` in `O(n)`.  
  - **Total complexity:** **O(n log max(nums))**.  

- **Space Complexity:**  
  - **O(1)** (constant space, only variables used).  

---

# Code  

```cpp
class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int l = 0;
        int h = INT_MIN;
        for (auto i : nums) h = max(h, i);

        while (h - l > 1) {
            int mid = l + (h - l) / 2;
            if (valid(nums, k, mid)) 
                h = mid;  // Try for a smaller capability
            else 
                l = mid;  // Increase the capability
        }
        return h;  // Minimum required capability
    }

    bool valid(vector<int>& nums, int k, int mid) {
        int i = 0;
        int res = 0;
        while (i < nums.size()) {
            if (nums[i] <= mid) {  // If the house value is within capability
                res++;
                i += 2;  // Skip the next house to maintain non-adjacency
            } else {
                i++;
            }
        }
        return res >= k;  // Return true if we can rob at least k houses
    }
};

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