House Robber IV

Med

#2340Time: 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`.2 companies

Patterns

Dynamic Programming Greedy

Algorithms

Binary Search

Data structures

Array

Companies

LinkedIn Cashfree

Prompt

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 i^th 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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= (nums.length + 1)/2

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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].

Walkthrough

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):

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].
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.

1// This is a conceptual illustration. It will result in Time Limit Exceeded.2class Solution {3    public int minCapability(int[] nums, int k) {4        int n = nums.length;5        if (k == 0) return 0;6        7        // dp[i][j]: min capability to rob j houses from first i houses8        long[][] dp = new long[n + 1][k + 1];9        long INF = 2_000_000_000L; // Larger than max possible capability10 11        for (int j = 1; j <= k; j++) {12            dp[0][j] = INF;13        }14        for (int i = 0; i <= n; i++) {15            dp[i][0] = 0;16        }17 18        for (int i = 1; i <= n; i++) {19            for (int j = 1; j <= k; j++) {20                // Option 1: Don't rob house i-121                long option1 = dp[i - 1][j];22 23                // Option 2: Rob house i-124                long robCurrentHouseCap = nums[i - 1];25                long prevCap = (i >= 2) ? dp[i - 2][j - 1] : (j == 1 ? 0 : INF);26                long option2 = Math.max(robCurrentHouseCap, prevCap);27                28                dp[i][j] = Math.min(option1, option2);29            }30        }31        return (int)dp[n][k];32    }33}

Complexity

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`.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int minCapability(int[] nums, int k) {3        int left = 1, right = 1_000_000_000;4        int ans = right;5 6        while (left <= right) {7            int mid = left + (right - left) / 2;8            if (canRob(nums, k, mid)) {9                // mid is a possible capability, try for a smaller one10                ans = mid;11                right = mid - 1;12            } else {13                // mid is too small, need a larger capability14                left = mid + 1;15            }16        }17        return ans;18    }19 20    // Helper function to check if we can rob at least k houses with a given capability21    private boolean canRob(int[] nums, int k, int capability) {22        int housesRobbed = 0;23        int i = 0;24        while (i < nums.length) {25            if (nums[i] <= capability) {26                housesRobbed++;27                i += 2; // Rob this house and skip the next one28            } else {29                i++; // Cannot rob this house, move to the next30            }31        }32        return housesRobbed >= k;33    }34}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int minCapability(int[] nums, int k) {4    int left = 0, right = (int)1 e9;5    while (left < right) {6      int mid = (left + right) >> 1;7      if (f(nums, mid) >= k) {8        right = mid;9      } else {10        left = mid + 1;11      }12    }13    return left;14  }15private16  int f(int[] nums, int x) {17    int cnt = 0, j = -2;18    for (int i = 0; i < nums.length; ++i) {19      if (nums[i] > x || i == j + 1) {20        continue;21      }22      ++cnt;23      j = i;24    }25    return cnt;26  }27}

1class Solution {2public:3  int minCapability(vector<int> &nums, int k) {4    auto f = [&](int x) {5      int cnt = 0, j = -2;6      for (int i = 0; i < nums.size(); ++i) {7        if (nums[i] > x || i == j + 1) {8          continue;9        }10        ++cnt;11        j = i;12      }13      return cnt >= k;14    };15    int left = 0, right = *max_element(nums.begin(), nums.end());16    while (left < right) {17      int mid = (left + right) >> 1;18      if (f(mid)) {19        right = mid;20      } else {21        left = mid + 1;22      }23    }24    return left;25  }26};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem