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.
This approach uses dynamic programming to solve the problem. We define a DP array where dp[i] represents the minimum capability needed to rob at least k houses up to index i. We'll build this array by considering two choices: either rob the current house or skip it. Our goal is to find the minimum capability where k houses can be robbed without robbing adjacent houses.
This code initializes a DP array and updates it by iterating over the houses, deciding whether to rob or not at each step. Given the constraints, it finds the minimum possible maximum capability to rob at least k houses.
Time Complexity: O(n), Space Complexity: O(n)
This approach involves using binary search on the potential capability range and verifying the capability using a sliding window technique. The basic idea is to efficiently determine if it’s possible to rob at least k houses with a given capability, adjusting the capability through binary search.
This JavaScript solution first defines a helper function that checks the feasibility of robbing at least k houses with a given capability using a sliding window. Binary search adjusts the capability range to find the minimum.
JavaScript
C++
Time Complexity: O(n log m), where m is the range of money, Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), Space Complexity: O(n) |
| Binary Search with Sliding Window | Time Complexity: O(n log m), where m is the range of money, Space Complexity: O(1) |
| 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 |
House Robber IV - Leetcode 2560 - Python • NeetCodeIO • 14,977 views views
Watch 9 more video solutions →Practice House Robber IV with our built-in code editor and test cases.
Practice on FleetCode