Watch 10 video solutions for House Robber IV, a medium level problem involving Array, Binary Search. This walkthrough by NeetCodeIO has 14,977 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= nums[i] <= 1091 <= k <= (nums.length + 1)/2Problem Overview: You are given an array where each value represents money in a house. You must rob at least k houses without robbing adjacent houses. Instead of maximizing money, the goal is to minimize your capability — the maximum amount stolen from any robbed house.
Approach 1: Dynamic Programming (O(nk) time, O(nk) space)
This approach models the problem as selecting exactly k non-adjacent houses while minimizing the maximum value among chosen houses. Define dp[i][j] as the minimum possible capability when considering the first i houses and robbing j houses. For each house, you either skip it or take it (which forces you to skip the previous one). The transition compares the capability from skipping versus taking the house using max(nums[i], dp[i-2][j-1]). This solution clearly expresses the constraint logic but becomes expensive when k grows. Useful for understanding the structure of the problem and how adjacency constraints propagate through DP states. Related patterns appear often in array problems and classic dynamic programming selections.
Approach 2: Binary Search with Greedy Check (O(n log M) time, O(1) space)
The key insight: instead of directly choosing houses, search for the smallest capability value that still allows robbing at least k houses. If your capability is x, you can only rob houses with value ≤ x. The question becomes: can you pick k non-adjacent houses under that constraint?
Use binary search on the capability range between the minimum and maximum values in the array. For each candidate value, scan the array greedily. If nums[i] ≤ capability, rob it and skip the next index to maintain the non-adjacent rule. Count how many houses you can rob. If the count reaches k, the capability works; otherwise it is too small.
This works because feasibility is monotonic: if capability x allows robbing k houses, any capability larger than x will also work. Binary search exploits this monotonic property to find the minimum valid value efficiently. The greedy validation step runs in linear time and uses only a counter and index jumps.
Recommended for interviews: Binary search with greedy validation. Interviewers expect you to recognize the monotonic feasibility condition and convert the optimization objective into a decision problem. Showing the DP formulation first demonstrates problem understanding, but the binary search solution proves algorithmic maturity and achieves the optimal O(n log M) complexity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(nk) | O(nk) | When explicitly modeling the non-adjacent selection constraint or learning the DP formulation of the problem |
| Binary Search + Greedy Check | O(n log M) | O(1) | Optimal solution when capability range is large and feasibility can be checked in linear time |