✔️ Binary Search | Python | C++ | Java | JS | C# | Go | Swift | Rust | Kotlin
IntuitionThe robber's capability is defined as the maximum amount of money he steals from one house. We want to minimize this capability while ensuring the robb
# Intuition
The robber's capability is defined as the maximum amount of money he steals from one house. We want to minimize this capability while ensuring the robber steals from at least k houses. This is a problem where we can apply **binary search** on the answer.
The key insight is that if the robber can steal from at least k houses with a capability of x, then he can also do so with any capability > x. Conversely, if he cannot steal from k houses with capability x, then he cannot do so with any capability < x. This monotonicity makes the problem suitable for **binary search**.

# Approach
1. Use binary search on the possible capability values, which range from the minimum to maximum value in the nums array.
2. For each capability value `mid`, check if it's possible to steal at least `k` houses:
   - Create a greedy algorithm: always steal from the current house if its value is ≤ capability, then skip the adjacent house.
    - If we can steal at least `k` houses with this capability, try a lower capability (search in the left half).
    - Otherwise, search in the right half.
3. Return the minimum capability that allows stealing at least `k` houses.
# Complexity
- Time complexity: `O(n log m)` - where n is the length of nums and m is the maximum value in nums
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: `O(1)`
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        def can_steal_k_houses(capability):
            count = 0
            i = 0
            while i < len(nums):
                if nums[i] <= capability:
                    count += 1
                    i += 2 
                else:
                    i += 1
            return count >= k
        
        left, right = min(nums), max(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            if can_steal_k_houses(mid):
                right = mid
            else:
                left = mid + 1
                
        return left    
```
```cpp []
class Solution {
public:
    bool canStealKHouses(const vector<int>& nums, int k, int capability) {
        int count = 0;
        int i = 0;
        while (i < nums.size()) {
            if (nums[i] <= capability) {
                count++;
                i += 2; 
            } else {
                i++;
            }
        }
        return count >= k;
    }
    
    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 (canStealKHouses(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};
```
```java []
class Solution {
    private boolean canStealKHouses(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++;
            }
        }
        return count >= k;
    }
    
    public int minCapability(int[] nums, int k) {
        int left = Arrays.stream(nums).min().getAsInt();
        int right = Arrays.stream(nums).max().getAsInt();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canStealKHouses(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}
```
```javascript []
const minCapability = (nums, k) => {
    const canStealKHouses = (capability) => {
        let count = 0;
        let i = 0;
        while (i < nums.length) {
            if (nums[i] <= capability) {
                count++;
                i += 2;
            } else {
                i++;
            }
        }
        return count >= k;
    };
    
    let left = Math.min(...nums);
    let right = Math.max(...nums);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canStealKHouses(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
```
```csharp []
public class Solution {
    private bool CanStealKHouses(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++;
            }
        }
        return count >= k;
    }
    
    public int MinCapability(int[] nums, int k) {
        int left = nums.Min();
        int right = nums.Max();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (CanStealKHouses(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}
```
```go []
func canStealKHouses(nums []int, k, capability int) bool {
    count := 0
    i := 0
    for i < len(nums) {
        if nums[i] <= capability {
            count++
            i += 2
        } else {
            i++
        }
    }
    return count >= k
}

func minCapability(nums []int, k int) int {
    left, right := 1, math.MaxInt32
    
    for left < right {
        mid := left + (right-left)/2
        if canStealKHouses(nums, k, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return left
}
```
```swift []
class Solution {
    func minCapability(_ nums: [Int], _ k: Int) -> Int {
        func canStealKHouses(_ capability: Int) -> Bool {
            var count = 0
            var i = 0
            while i < nums.count {
                if nums[i] <= capability {
                    count += 1
                    i += 2
                } else {
                    i += 1
                }
            }
            return count >= k
        }
        
        var left = nums.min()!
        var right = nums.max()!
        
        while left < right {
            let mid = left + (right - left) / 2
            if canStealKHouses(mid) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        
        return left
    }
}
```
```rust []
impl Solution {
    pub fn min_capability(nums: Vec<i32>, k: i32) -> i32 {
        fn can_steal_k_houses(nums: &Vec<i32>, k: i32, capability: i32) -> bool {
            let mut count = 0;
            let mut i = 0;
            while i < nums.len() {
                if nums[i] <= capability {
                    count += 1;
                    i += 2;
                } else {
                    i += 1;
                }
            }
            count >= k
        }

        let mut left = *nums.iter().min().unwrap();
        let mut right = *nums.iter().max().unwrap();

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

        left
    }
}
```
```kotlin []
class Solution {
    fun minCapability(nums: IntArray, k: Int): Int {
        fun canStealKHouses(capability: Int): Boolean {
            var count = 0
            var i = 0
            while (i < nums.size) {
                if (nums[i] <= capability) {
                    count++
                    i += 2
                } else {
                    i++
                }
            }
            return count >= k
        }

        var left = nums.minOrNull() ?: 0
        var right = nums.maxOrNull() ?: 0

        while (left < right) {
            val mid = left + (right - left) / 2
            if (canStealKHouses(mid)) {
                right = mid
            } else {
                left = mid + 1
            }
        }

        return left
    }
}
```

---

![upvote.png](https://assets.leetcode.com/users/images/cbe52304-e9e1-494b-b799-e04ba3859d56_1742000318.51569.png)

['Binary Search', 'Swift', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'Kotlin', 'JavaScript', 'C#']