House Robber IV solution and explanation
Google
9 more videos on this problem
House Robber IV - Leetcode 2560 - PythonNeetCodeIO · 21:30 · 15K views
House Robber IV | Brute Force | Optimal | Leetcode 2560 | codestorywithMIKcodestorywithMIK · 38:12 · 13K views
House Robber IV | Leetcode 2560Techdose · 26:34 · 7K views
2560. House Robber IV | Binary Search on AnswerAryan Mittal · 16:27 · 3K views
2560. House Robber IV | LeetCode MediumDeep Tech · 13:15 · 3K views
2560. House Robber IV | LEETCODE Weekly 331 | BINARY SEARCHcode Explainer · 9:20 · 3K views
2560. House Robber IV (Leetcode Medium)Programming Live with Larry · 9:01 · 1K views
Leetcode 2560: House Robber IVAlgorithms Casts · 17:57 · 956 views
[Beats 100% Solution] 2560. House Robber IV [LeetCode Weekly Contest]TheGrayMind · 20:12 · 584 views
LeetCode 2560 - House Robber IV - JavaAlpha-Code · 8:47 · 118 views
The 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 <= 1051 <= nums[i] <= 1091 <= k <= (nums.length + 1)/2
Approach overview
Problem 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 1: Dynamic Programming Approach
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.
def minCapability(nums, k):
n = len(nums)
dp = [0] * (n + 1)
dp[0], dp[1] = nums[0], nums[0]
for i in range(2, n):
dp[i] = min(dp[i-1], max(dp[i-2] + nums[i], dp[i-1]))
return dp[n-1]public int minCapability(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n + 1];
dp[0] = nums[0];
dp[1] = nums[0];
for (int i = 2; i < n; i++) {
dp[i] = Math.min(dp[i-1], Math.max(dp[i-2] + nums[i], dp[i-1]));
}
return dp[n-1];
}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)
Approach 2: Binary Search with Sliding Window
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.
#include <vector>
#include <algorithm>
class Solution {
public:
int minCapability(std::vector<int>& nums, int k) {
auto canRobWithCapability = [&nums, k](int cap) {
int count = 0, i = 0;
while (i < nums.size()) {
if (nums[i] <= cap) {
count++;
i++;
}
if (count >= k) return true;
i++;
}
return false;
};
int low = *std::min_element(nums.begin(), nums.end());
int high = *std::max_element(nums.begin(), nums.end());
while (low < high) {
int mid = low + (high - low) / 2;
if (canRobWithCapability(mid)) high = mid;
else low = mid + 1;
}
return low;
}
};function minCapability(nums, k) {
function canRobWithCapability(cap) {
let count = 0, i = 0;
while (i < nums.length) {
if (nums[i] <= cap) {
count++;
i++;
}
if (count >= k) return true;
i++;
}
return false;
}
let low = Math.min(...nums), high = Math.max(...nums);
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (canRobWithCapability(mid)) high = mid;
else low = mid + 1;
}
return low;
}In this C++ solution, a lambda function checks if it’s possible to rob with a given capability. Using binary search, it minimizes the capability required over the maximum possible range.
Time Complexity: O(n log m), where m is the range of money, Space Complexity: O(1)
Approach 3: Binary Search + Greedy
The problem is asking for the minimum stealing ability of the thief. We can use binary search to enumerate the stealing ability of the thief. For the enumerated ability x, we can use a greedy approach to determine whether the thief can steal at least k houses. Specifically, we traverse the array from left to right. For the current house i we are traversing, if nums[i] leq x and the difference between the index of i and the last stolen house is greater than 1, then the thief can steal house i. Otherwise, the thief cannot steal house i. We accumulate the number of stolen houses. If the number of stolen houses is greater than or equal to k, it means that the thief can steal at least k houses, and at this time, the stealing ability x of the thief might be the minimum. Otherwise, the stealing ability x of the thief is not the minimum.
The time complexity is O(n times log m), and the space complexity is O(1). Where n and m are the length of the array nums and the maximum value in the array nums, respectively.
function minCapability(nums: number[], k: number): number {
const f = (mx: number): boolean => {
let cnt = 0;
let j = -2;
for (let i = 0; i < nums.length; ++i) {
if (nums[i] <= mx && i - j > 1) {
++cnt;
j = i;
}
}
return cnt >= k;
};
let left = 1;
let right = Math.max(...nums);
while (left < right) {
const mid = (left + right) >> 1;
if (f(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}func minCapability(nums []int, k int) int {
return sort.Search(1e9+1, func(x int) bool {
cnt, j := 0, -2
for i, v := range nums {
if v > x || i == j+1 {
continue
}
cnt++
j = i
}
return cnt >= k
})
}Complexity comparison
| 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) |
| Binary Search + Greedy | – |
Complexity analysis
| 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 |
Frequently asked questions
Is House Robber IV easy or hard?
House Robber IV is considered a medium difficulty problem. The challenge is recognizing that the objective can be converted into a monotonic decision problem and solved using binary search instead of traditional profit-maximization dynamic programming.
House Robber IV Python/Java solution
Most implementations use binary search with a helper function that checks feasibility in O(n). Python, Java, C++, and JavaScript versions follow the same structure: binary search the capability range and greedily count how many houses can be robbed without choosing adjacent ones.
How to solve House Robber IV in O(n)?
The greedy feasibility check itself runs in O(n). You iterate through the array and greedily rob a house if its value is within the current capability, then skip the next index to avoid adjacency. Combined with binary search on the capability range, the full algorithm becomes O(n log M).
What is the best approach for House Robber IV?
Binary search combined with a greedy feasibility check is the most efficient approach. Instead of choosing houses directly, search for the smallest robbery capability that still allows selecting at least k non-adjacent houses. Each feasibility check scans the array once, leading to O(n log M) time where M is the value range.
Is House Robber IV asked at Google/Amazon/Meta?
House Robber style problems frequently appear in interviews at companies like Amazon, Google, and Meta because they test dynamic programming, greedy reasoning, and constraint handling. Variants such as House Robber I, II, III, and IV are common practice problems for these interviews.
What data structure is used in House Robber IV?
The problem primarily uses arrays and binary search over numeric ranges. The optimal solution relies on a greedy scan of the array to count valid non-adjacent houses, while alternative formulations may use dynamic programming tables.
What is the time complexity of House Robber IV?
The optimal solution runs in O(n log M) time and O(1) space. Binary search determines the minimum capability, and each iteration performs a linear scan to count how many non-adjacent houses can be robbed under that capability limit.