#2560

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

House Robber IV

House Robber IV requires calculating minimum maximum money the robber can take using state transition dynamic programming and binary search.

array binary search dynamic programming greedy

Problem Statement

Given a row of houses where each house contains a certain amount of money, you need to select at least k houses to rob such that no two robbed houses are adjacent. The robber's capability is defined as the largest amount of money taken from any single robbed house. Determine the minimum capability needed to rob at least k houses.

You are provided an integer array nums where nums[i] represents the money in the ith house. The task is to find the minimum possible value of the robber's capability, ensuring at least k houses are robbed with no two robbed houses next to each other. Constraints: 1 <= nums.length <= 105, 1 <= nums[i] <= 109, 1 <= k <= (nums.length + 1)/2.

Examples

Example 1

Input: nums = [2,3,5,9], k = 2

Output: 5

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

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

Solution Approach

Binary Search on Capability

We can binary search the minimum possible capability between the smallest and largest money in nums. For each candidate value mid, we check if it is feasible to rob at least k houses without taking any house exceeding mid.

State Transition Dynamic Programming Check

To check feasibility for a given capability, iterate through nums and simulate robbing houses that do not exceed mid. Use a greedy selection with state transitions: either rob current house (skip next) or skip it. Count the number of houses robbed to verify if it meets or exceeds k.

Return Minimum Valid Capability

Continue the binary search, narrowing the range based on feasibility. Once the search converges, the lower bound represents the minimum capability needed to rob at least k houses while respecting the non-adjacent constraint.

Complexity Analysis

Metric	Value
Time	O(n \log m)
Space	O(1)

Time complexity is O(n log m), where n is nums.length and m is the range of money values, due to binary search and linear scan feasibility check. Space complexity is O(1) as we only maintain counters and current state.

What Interviewers Usually Probe

Candidate immediately considers binary search combined with DP feasibility check.
Explains state transition clearly: rob or skip each house depending on candidate capability.
Considers edge cases where k is maximum possible given array length.

Common Pitfalls or Variants

Common pitfalls

Failing to enforce non-adjacent house constraint when counting houses for feasibility.
Using full DP arrays causing unnecessary O(n) space instead of constant space.
Not correctly updating binary search bounds leading to off-by-one errors in minimum capability.

Follow-up variants

Minimize capability for robbing exactly k houses instead of at least k.
Rob houses with circular adjacency constraint, first and last house considered adjacent.
Rob houses with variable adjacency distances, e.g., at least d houses apart instead of 1.

FAQ

What pattern does House Robber IV follow?

It follows state transition dynamic programming combined with binary search to find minimum feasible capability.

How do I check if a candidate capability is valid?

Simulate robbing houses that do not exceed the candidate value using DP-style transitions, ensuring no adjacent houses are robbed, and count successful robberies.

Can this approach handle large nums arrays?

Yes, binary search with linear feasibility check gives O(n log m) time, suitable for up to 105 houses.

Why is binary search needed in House Robber IV?

Binary search efficiently finds the minimum maximum money the robber can take without checking all subsets of houses.

Does the greedy check always guarantee minimum capability?

Yes, when combined with binary search, the greedy feasibility check ensures the lowest maximum value is found while robbing at least k houses.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#2616 minimize the maximum difference of pairs #2439 minimize maximum of array #1671 minimum number of removals to make mountain array