# House Robber IV
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/house-robber-iv)
Canonical: https://scaleengineer.com/dsa/problems/house-robber-iv
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [Cashfree](https://scaleengineer.com/companies/cashfree)
---
## Problem
There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he **refuses to steal from adjacent homes**.

The **capability** of the robber is the maximum amount of money he steals from one house of all the houses he robbed.

You are given an integer array `nums` representing how much money is stashed in each house. More formally, the `ith` house from the left has `nums[i]` dollars.

You are also given an integer `k`, representing the **minimum** number of houses the robber will steal from. It is always possible to steal at least `k` houses.

Return _the **minimum** capability of the robber out of all the possible ways to steal at least_ `k` _houses_.

**Example 1:**

**Input:** nums = [2,3,5,9], k = 2
**Output:** 5
**Explanation:** 
There are three ways to rob at least 2 houses:
- Rob the houses at indices 0 and 2. Capability is max(nums[0], nums[2]) = 5.
- Rob the houses at indices 0 and 3. Capability is max(nums[0], nums[3]) = 9.
- Rob the houses at indices 1 and 3. Capability is max(nums[1], nums[3]) = 9.
Therefore, we return min(5, 9, 9) = 5.

**Example 2:**

**Input:** nums = [2,7,9,3,1], k = 2
**Output:** 2
**Explanation:** There are 7 ways to rob the houses. The way which leads to minimum capability is to rob the house at index 0 and 4. Return max(nums[0], nums[4]) = 2.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`
* `1 <= k <= (nums.length + 1)/2`

# Approaches
## Dynamic Programming
This approach uses dynamic programming to build the solution from smaller subproblems. We define a state `dp[i][j]` as the minimum capability required to rob exactly `j` non-adjacent houses from the first `i` available houses. By computing the values for this state iteratively, we can determine the minimum capability for robbing `k` houses from the entire array.
**Time:** O(n * k), where `n` is the number of houses and `k` is the number of houses to rob. We fill a DP table of size `(n+1) x (k+1)`. · **Space:** O(n * k). This can be optimized to O(k) because the calculation for row `i` only depends on rows `i-1` and `i-2`.
**Pros:** Provides a structured way to solve the problem by breaking it down into subproblems.; Guaranteed to find the correct answer for smaller inputs.
**Cons:** The time complexity of O(n * k) is too slow for the given constraints, where `n` can be up to 10^5 and `k` can be up to `n/2`. This will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
We can formulate a solution using a 2D DP table, `dp[i][j]`, where `i` corresponds to the number of houses considered from the start of the array, and `j` is the number of houses we need to rob.

The state `dp[i][j]` will store the minimum capability to rob `j` houses from the subarray `nums[0...i-1]`.

The recurrence relation is derived by considering two choices for the `i`-th house (at index `i-1`):

1.  **Don't rob house `i`**: If we don't rob the current house, the problem reduces to robbing `j` houses from the first `i-1` houses. The minimum capability required for this is simply `dp[i-1][j]`.
2.  **Rob house `i`**: If we rob the current house, we cannot have robbed the previous house (`i-1`). This means we must have robbed `j-1` houses from the first `i-2` houses. The capability for this new set of robberies is determined by the largest value among the robbed houses, which is `max(nums[i-1], dp[i-2][j-1])`.

The value of `dp[i][j]` is the minimum of these two options. The final answer is `dp[n][k]`. While correct, this approach is not efficient enough for the problem's constraints.

```java
// This is a conceptual illustration. It will result in Time Limit Exceeded.
class Solution {
    public int minCapability(int[] nums, int k) {
        int n = nums.length;
        if (k == 0) return 0;
        
        // dp[i][j]: min capability to rob j houses from first i houses
        long[][] dp = new long[n + 1][k + 1];
        long INF = 2_000_000_000L; // Larger than max possible capability

        for (int j = 1; j <= k; j++) {
            dp[0][j] = INF;
        }
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                // Option 1: Don't rob house i-1
                long option1 = dp[i - 1][j];

                // Option 2: Rob house i-1
                long robCurrentHouseCap = nums[i - 1];
                long prevCap = (i >= 2) ? dp[i - 2][j - 1] : (j == 1 ? 0 : INF);
                long option2 = Math.max(robCurrentHouseCap, prevCap);
                
                dp[i][j] = Math.min(option1, option2);
            }
        }
        return (int)dp[n][k];
    }
}
```
### Algorithm
- Initialize a 2D array `dp` of size `(n+1) x (k+1)` with a very large value (infinity) to store the minimum capabilities.
- Set the base cases: `dp[i][0] = 0` for all `i`, as robbing zero houses requires zero capability.
- Iterate `i` from 1 to `n` (representing the first `i` houses).
- Inside, iterate `j` from 1 to `k` (representing the number of houses to rob).
- For each `dp[i][j]`, calculate the value based on two choices for house `i-1`:
  1. **Don't rob house `i-1`**: The capability is inherited from the solution for the first `i-1` houses, i.e., `dp[i-1][j]`.
  2. **Rob house `i-1`**: This is only possible if we didn't rob house `i-2`. The capability will be the maximum of the current house's value (`nums[i-1]`) and the capability required to rob `j-1` houses from the first `i-2` houses (`dp[i-2][j-1]`).
- The recurrence relation is `dp[i][j] = min(option1, option2)`.
- The final answer is `dp[n][k]`.

## Binary Search on the Answer
This optimal approach reframes the problem from finding the minimum capability to checking if a given capability is feasible. This allows us to use binary search on the answer. The key observation is that the problem has a monotonic property: if we can rob `k` houses with a capability of `C`, we can certainly do so with any capability `C' > C`. This allows us to efficiently search for the smallest possible `C`.
**Time:** O(N * log(M)), where N is the number of houses and M is the range of possible money values (the search space for capability, e.g., 10^9). The `canRob` helper function takes O(N), and it's called O(log(M)) times by the binary search. · **Space:** O(1), as the algorithm only requires a few variables for the binary search and the greedy check, independent of the input size.
**Pros:** Highly efficient with a time complexity of O(N log M), which easily passes the given constraints.; The space complexity is optimal at O(1).; The greedy check function is simple to reason about and implement.
**Cons:** The core idea of applying binary search to the answer space might not be immediately obvious.
### Explanation
The problem asks for the *minimum* capability that satisfies a certain condition. This structure is a perfect fit for **Binary Search on the Answer**.

The range of possible answers for the capability is between the minimum and maximum money values in the `nums` array. We can binary search within this range (e.g., from 1 to 10^9 based on constraints).

For each `mid` value (a potential capability) in our binary search, we must verify if it's possible to rob at least `k` houses where each house has `nums[i] <= mid`. This verification can be done with a simple and efficient greedy helper function, `canRob(capability)`.

**The `canRob(capability)` function:**
This function greedily determines the maximum number of non-adjacent houses we can rob under the given `capability` constraint. We iterate through the houses from left to right:
- If `nums[i] <= capability`, it's a house we can potentially rob. To maximize the number of houses, we should rob it. We increment our count of robbed houses and then skip the next house (`i+1`) because of the non-adjacent rule.
- If `nums[i] > capability`, we cannot rob this house, so we simply move on.
If, after checking all houses, the total count of robbed houses is at least `k`, the function returns `true`.

By combining binary search with this greedy check, we can find the minimum capability in an efficient manner.

```java
class Solution {
    public int minCapability(int[] nums, int k) {
        int left = 1, right = 1_000_000_000;
        int ans = right;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canRob(nums, k, mid)) {
                // mid is a possible capability, try for a smaller one
                ans = mid;
                right = mid - 1;
            } else {
                // mid is too small, need a larger capability
                left = mid + 1;
            }
        }
        return ans;
    }

    // Helper function to check if we can rob at least k houses with a given capability
    private boolean canRob(int[] nums, int k, int capability) {
        int housesRobbed = 0;
        int i = 0;
        while (i < nums.length) {
            if (nums[i] <= capability) {
                housesRobbed++;
                i += 2; // Rob this house and skip the next one
            } else {
                i++; // Cannot rob this house, move to the next
            }
        }
        return housesRobbed >= k;
    }
}
```
### Algorithm
- Define a search range for the capability. The lower bound `left` can be 1, and the upper bound `right` can be the maximum possible value of money in a house (10^9).
- Start a binary search loop while `left <= right`.
- In each iteration, calculate the middle value `mid = left + (right - left) / 2`. This `mid` is our candidate for the minimum capability.
- Create a helper function `canRob(capability)` that checks if it's possible to rob at least `k` houses with the given `capability`.
- The `canRob` function works greedily: Iterate through the houses. If `nums[i] <= capability`, we rob this house, increment a counter, and skip the next house (`i += 2`). Otherwise, we cannot rob it and move to the next house (`i++`). The function returns `true` if the counter is at least `k`.
- If `canRob(mid)` is `true`, it means `mid` is a valid capability. We might find an even smaller one, so we record `mid` as a potential answer and search in the lower half: `ans = mid`, `right = mid - 1`.
- If `canRob(mid)` is `false`, the capability `mid` is too restrictive. We need a larger capability, so we search in the upper half: `left = mid + 1`.
- After the loop terminates, `ans` will hold the minimum capability found.

# Solutions
### Java

```java
class Solution {
public
  int minCapability(int[] nums, int k) {
    int left = 0, right = (int)1 e9;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (f(nums, mid) >= k) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
private
  int f(int[] nums, int x) {
    int cnt = 0, j = -2;
    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] > x || i == j + 1) {
        continue;
      }
      ++cnt;
      j = i;
    }
    return cnt;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minCapability(vector<int> &nums, int k) {
    auto f = [&](int x) {
      int cnt = 0, j = -2;
      for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] > x || i == j + 1) {
          continue;
        }
        ++cnt;
        j = i;
      }
      return cnt >= k;
    };
    int left = 0, right = *max_element(nums.begin(), nums.end());
    while (left < right) {
      int mid = (left + right) >> 1;
      if (f(mid)) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
};

```

### Python

```python
class Solution:
    def minCapability(self, nums: List[int], k: int) -> int: def f(x): cnt, j = 0, - 2 for i, v in enumerate(nums): if v > x or i == j + 1: continue cnt += 1 j = i return cnt >= k return bisect_left(range(max(nums) + 1), True, key=f)

```