Simple C Solution with explanation! | beats 100%✅ | Greedy + Binary-Search |
Intuition
We need to find the minimum possible maximum house value that allows us to rob exactly k houses without robbing two adjacent houses.
Since the maximum
# Intuition
- We need to find the minimum possible maximum house value that allows us to rob exactly `k` houses without robbing two adjacent houses. 
- Since the maximum house value directly affects the number of houses we can rob, we can use **binary search** to efficiently determine the optimal value.
---
# Approach
1. **Binary Search on Capacity**:  
   - We define a range `[left, right]`, where `left` is the minimum house value and `right` is the maximum house value in `nums`.
   - The mid value represents a **potential max value** for a house that can be robbed.
   
2. **Check Feasibility with a Greedy Approach**:  
   - We iterate through `nums`, trying to **rob the maximum number of non-adjacent houses** without exceeding `mid`.
   - If we can rob at least `k` houses, we try to minimize `mid` further.
   - Otherwise, we increase `mid` to allow robbing more houses.

3. **Return the Smallest Valid `mid`**:  
   - The first value of `mid` that allows robbing at least `k` houses is our answer.
---
# Complexity
- ### **Time complexity**:  $$O(n \log M)$$  
  - Binary search runs in $$O(\log M)$$, where `M` is the maximum value in `nums`.
  - Checking feasibility via a greedy scan takes $$O(n)$$.
  - Total complexity: $$O(n \log M)$$.

- ### **Space complexity**: $$O(1)$$  
  - We only use a few integer variables for binary search and iteration.

---

# Code
```c []
int helper(int *nums, int numsSize, int capacity) {
    int stolen = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] <= capacity) {
            stolen++;
            i++;
        }
    }
    return stolen;
}
int minCapability(int* nums, int numsSize, int k) {
    if (!nums || numsSize <= 0) return -1;
    
    int left  = nums[0];
    int right = nums[0];

    for (int i = 0; i < numsSize; i++) {
        left  = (nums[i] < left ) ? nums[i] : left;
        right = (nums[i] > right) ? nums[i] : right;
    }

    int mid;
    while (left < right) {
        mid = (left + right) / 2;
        if (helper(nums, numsSize, mid) >= k) right = mid;
        else left = mid + 1;
    }

    return left;
}
```
['Array', 'Binary Search', 'Dynamic Programming', 'Greedy', 'C']