Expected Method ✅| Binary Search on Answer 2️⃣| Detail Explaination| Java,Python
Problem: Minimum Capability to Steal from HousesGiven an array nums[], where nums[i] represents the money in the i-th house, and an integer k (the number of hou
## **Problem: Minimum Capability to Steal from Houses**  
Given an array `nums[]`, where `nums[i]` represents the **money in the `i-th` house**, and an integer `k` (the number of houses to rob), determine the **minimum maximum money stolen from any one house** such that exactly `k` houses are robbed.  
- **Condition:** The robber **cannot rob two adjacent houses**.  

---

## **Intuition**  
- We need to rob exactly `k` houses while **minimizing the maximum amount stolen from any single house**.
- This suggests a **binary search** on the range `[min(nums[]), max(nums[])]` to find the lowest possible maximum money (`cap`) that allows robbing `k` houses.

---

## **Approach**  
### **1. Define the Binary Search Range**
- **Lower Bound (`l`)**: The minimum amount in `nums[]`.  
- **Upper Bound (`r`)**: The maximum amount in `nums[]`.  
- **Goal**: Find the minimum `cap` such that exactly `k` houses can be robbed **without adjacent house selection**.

### **2. Check Feasibility (`isPossible` function)**
- **For a given `cap` (mid value of binary search)**:  
  - Traverse `nums[]`, greedily selecting houses where `nums[i] ≤ cap`.  
  - If we rob a house at index `i`, skip the next house (`i+1`).  
  - **Count the number of houses robbed (`cnt`)**.  
  - If `cnt ≥ k`, `cap` is **feasible**, so try a smaller `cap` (`r = mid - 1`).  
  - Otherwise, increase `cap` (`l = mid + 1`).

---

## **Iterative Execution with Edge Cases**
### **Example 1: Basic Case**  
#### **Input:**  
```plaintext
nums = [2, 3, 5, 9]
k = 2
```
#### **Step-by-Step Execution**  
1. **Initial Conditions**  
   - `l = min(nums) = 2`, `r = max(nums) = 9`
   - **Binary search range**: `[2, 9]`

2. **Binary Search Iterations**
   | Iteration | mid | Feasible? | Update `l` or `r` | Explanation |
   |-----------|-----|-----------|----------------|--------------|
   | 1         | 5   | ✅ Yes | r = 4 | We can rob houses `[2, 5]` (or `[3, 5]`). |
   | 2         | 3   | ✅ Yes | r = 2 | We can rob `[2, 3]`. |
   | 3         | 2   | ✅ Yes | r = 1 | We can rob `[2, 5]` (same as before). |

   **Final Answer:** `2`

---

### **Example 2: Edge Case - Large Values**
#### **Input:**  
```plaintext
nums = [5, 1, 8, 3, 6]
k = 3
```
#### **Step-by-Step Execution**  
1. **Initial Conditions**  
   - `l = min(nums) = 1`, `r = max(nums) = 8`
   - **Binary search range**: `[1, 8]`

2. **Binary Search Iterations**
   | Iteration | mid | Feasible? | Update `l` or `r` |
   |-----------|-----|-----------|----------------|
   | 1         | 4   | ✅ Yes | r = 3 |
   | 2         | 2   | ✅ Yes | r = 1 |
   | 3         | 1   | ❌ No | l = 2 |

   **Final Answer:** `2`

---
## **Complexity Analysis**
- **Time Complexity:** $$ O(N \log M) $$  
  - $$ N $$ = number of houses.  
  - $$ M $$ = range of values in `nums[]`.  
  - **Binary search** takes $$ O(\log M) $$, and checking feasibility per iteration takes $$ O(N) $$.  

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

---
![images.jpg](https://assets.leetcode.com/users/images/c30a55da-12be-40f6-b8ac-9af668597edd_1742058827.8020747.jpeg)


## **Code**
```java []
class Solution {
    public boolean isPossible(int[] nums, int k, int cap) {
        int cnt = 0, i = 0;
        while (i < nums.length) {
            if (nums[i] <= cap) { 
                cnt++;  // Rob this house
                i++;  // Skip the next house
            }
            i++;  // Move to next house
        }
        return cnt >= k;  // Return true if we can rob at least k houses
    }

    public int minCapability(int[] nums, int k) {
        int l = Integer.MAX_VALUE, r = 0;
        for (int i : nums) {
            r = Math.max(r, i);
            l = Math.min(l, i);
        }
        while (l <= r) {
            int mid = (l + r) / 2;
            if (isPossible(nums, k, mid)) {
                r = mid - 1;  // Try a smaller capability
            } else {
                l = mid + 1;  // Increase capability
            }
        }
        return l;  // Return the lowest feasible max amount
    }
}
```

```python []
class Solution:
    def isPossible(self, nums, k, cap):
        cnt = 0
        i = 0
        while i < len(nums):
            if nums[i] <= cap:
                cnt += 1  # Rob this house
                i += 1  # Skip the next house
            i += 1  # Move to next house
        return cnt >= k

    def minCapability(self, nums: List[int], k: int) -> int:
        l, r = min(nums), max(nums)

        while l <= r:
            mid = (l + r) // 2
            if self.isPossible(nums, k, mid):
                r = mid - 1
            else:
                l = mid + 1
        return l
```
['Array', 'Binary Search', 'Java', 'Python3']