Skip to main content
Talentd

House Robber IV - Solution & Explanation

MediumArrayBinary Search13 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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

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.

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.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n), Space Complexity: O(n)

Try this approach in the editor →

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.

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.

Code

JavaScriptC++

JavaScript

C++

Complexity

Time Complexity: O(n log m), where m is the range of money, Space Complexity: O(1)

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic ProgrammingO(nk)O(nk)When explicitly modeling the non-adjacent selection constraint or learning the DP formulation of the problem
Binary Search + Greedy CheckO(n log M)O(1)Optimal solution when capability range is large and feasibility can be checked in linear time

Video Solution

House Robber IV - Leetcode 2560 - Python • NeetCodeIO • 15,633 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice House Robber IV with our built-in code editor and test cases.

Practice on FleetCode
Previous

Container With Most Water

Next

House Robber