🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏| JAVA | C | C++ | PYTHON| JAVASCRIPT | DART 
IntuitionWe are given a list of houses, each with some amount of money, and we can only rob non-adjacent houses. We need to find the minimum capability required
![image.png](https://assets.leetcode.com/users/images/05781b7d-e207-4278-ba04-fb300714df23_1742014064.7628481.png)

----
![1000119952.png](https://assets.leetcode.com/users/images/057910cd-ded7-486a-91f9-b1142419063e_1742026267.1927934.png)

![1000119954.png](https://assets.leetcode.com/users/images/6886cd78-b869-439c-b42f-a9edfd345a2d_1742026275.5942228.png)


![1000119956.png](https://assets.leetcode.com/users/images/8112d92c-d2b2-4bd9-a9d6-79f6ed95816c_1742026283.3625941.png)



-----



# **Intuition**  
We are given a list of houses, each with some amount of money, and we can only rob non-adjacent houses. We need to find the **minimum capability** required such that we can rob **at least `k` houses** while ensuring the house we rob does not have more money than our capability.  

The key idea is to **binary search** on the capability (maximum money a house can have while still being robbed).

---

# **Approach**  
1. **Binary Search Setup:**  
   - The possible range for capability is `[min(nums), max(nums)]`.  
   - The left boundary `left` is the **minimum** house value (since we must rob at least `k` houses).  
   - The right boundary `right` is the **maximum** house value (if capability is set to this, we can rob all valid houses).  

2. **Binary Search Execution:**  
   - Calculate `mid = (left + right) / 2`, treating it as the potential **capability**.  
   - Check if we can rob at least `k` houses without breaking the **non-adjacent rule** using `canRob()`.  
   - If we can rob `k` houses with `mid` capability, we try a **smaller capability (`right = mid`)**.  
   - Otherwise, increase the **capability (`left = mid + 1`)**.  

3. **Checking Feasibility (`canRob` function):**  
   - Iterate through `nums`, and when `nums[i] ≤ capability`, count it as a **robbed house** and **skip the next house (i += 2)** to maintain the **non-adjacent constraint**.  
   - If we rob at least `k` houses, return `true`.  

---

# **Complexity**  
- **Time Complexity:**  
  - **Binary search** runs in **O(log M)**, where `M` is the range `[min(nums), max(nums)]`.  
  - Checking feasibility (`canRob`) takes **O(N)**.  
  - **Total Complexity:** **O(N log M)**.  

- **Space Complexity:** **O(1)** (No extra space used apart from variables).  

---


```dart []
class Solution {
  int minCapability(List<int> nums, int k) {
    int left = nums.reduce((a, b) => a < b ? a : b);
    int right = nums.reduce((a, b) => a > b ? a : b);

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

    return left;
  }

  bool canRob(List<int> nums, int k, int capability) {
    int count = 0;
    int i = 0;

    while (i < nums.length) {
      if (nums[i] <= capability) {
        count++;
        i += 2;
      } else {
        i++;
      }

      if (count >= k) return true;
    }

    return count >= k;
  }
}
```


```java []
class Solution {
    public int minCapability(int[] nums, int k) {
        int left = Integer.MAX_VALUE, right = Integer.MIN_VALUE;
        for (int num : nums) {
            left = Math.min(left, num);
            right = Math.max(right, num);
        }

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

        return left;
    }

    private boolean canRob(int[] nums, int k, int capability) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= capability) {
                count++;
                i++; // Skip next house
            }
            if (count >= k) return true;
        }
        return count >= k;
    }
}
```


```cpp []
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int left = *min_element(nums.begin(), nums.end());
        int right = *max_element(nums.begin(), nums.end());

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

        return left;
    }

private:
    bool canRob(vector<int>& nums, int k, int capability) {
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] <= capability) {
                count++;
                i++; // Skip next house
            }
            if (count >= k) return true;
        }
        return false;
    }
};
```


```python []
from typing import List

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        left, right = min(nums), max(nums)

        while left < right:
            mid = (left + right) // 2
            if self.canRob(nums, k, mid):
                right = mid
            else:
                left = mid + 1
        
        return left

    def canRob(self, nums: List[int], k: int, capability: int) -> bool:
        count, i = 0, 0
        while i < len(nums):
            if nums[i] <= capability:
                count += 1
                i += 2
            else:
                i += 1
            if count >= k:
                return True
        return count >= k
```


```javascript []
var minCapability = function(nums, k) {
    let left = Math.min(...nums), right = Math.max(...nums);

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canRob(nums, k, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
};

function canRob(nums, k, capability) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] <= capability) {
            count++;
            i++; // Skip next house
        }
        if (count >= k) return true;
    }
    return false;
}
```


-----



![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}
['Array', 'Binary Search', 'C', 'Python', 'C++', 'Java', 'Python3', 'JavaScript', 'Dart', 'Python ML']