Problem Description

You have a row of consecutive houses along a street, where each house contains some money. A robber wants to steal from these houses, but has one strict rule: he cannot steal from two adjacent houses.

Given:

• An integer array nums where nums[i] represents the amount of money in the i-th house
• An integer k representing the minimum number of houses the robber must steal from

The capability of the robber is defined as the maximum amount of money he takes from any single house among all the houses he robs.

Your task is to find the minimum possible capability that allows the robber to steal from at least k houses while never robbing adjacent houses.

For example, if nums = [2, 3, 5, 9] and k = 2:

• If the robber steals from houses with values 2 and 5, his capability is max(2, 5) = 5
• If the robber steals from houses with values 2 and 9, his capability is max(2, 9) = 9
• If the robber steals from houses with values 3 and 9, his capability is max(3, 9) = 9

The minimum capability would be 5 in this case.

The problem guarantees it's always possible to steal from at least k houses following the non-adjacent rule.

Intuition

The key insight is recognizing that this is an optimization problem where we need to find the minimum value of something (capability) that satisfies a constraint (robbing at least k houses).

Think about it this way: if we fix a capability value x, we can ask ourselves - "Can the robber steal from at least k houses without exceeding this capability?" This becomes a yes/no question. If the answer is yes, we might be able to do better with a smaller capability. If the answer is no, we need a larger capability.

This binary nature of the problem (yes/no for each capability value) suggests using binary search. The capability must be between the minimum and maximum values in the array. We can search this range to find the smallest capability that works.

For a given capability x, how do we check if it's possible to rob k houses? We want to maximize the number of houses we can rob while staying within capability x. A greedy approach works here: go through the houses from left to right, and whenever we see a house with value ≤ x that isn't adjacent to the last house we robbed, we should rob it. Why? Because robbing it now doesn't prevent us from robbing better houses later - we're just trying to maximize the count of houses robbed.

The beauty of this approach is that binary search naturally finds the minimum capability. As we search, we keep lowering our capability threshold whenever we find it's possible to rob k houses, eventually converging on the minimum possible value.

Learn more about Greedy, Binary Search and Dynamic Programming patterns.

Solution Approach

The solution combines binary search with a greedy validation function to find the minimum capability.

Binary Search Setup: We search for the minimum capability in the range [0, max(nums)]. The capability cannot exceed the maximum value in the array since that's the most money in any single house.

Validation Function f(x): For a given capability x, we check if the robber can steal from at least k houses:

1. Initialize a counter cnt = 0 for houses robbed and j = -2 to track the index of the last robbed house (starting at -2 ensures the first house can always be considered)
2. Iterate through each house i with value v:
   • Skip this house if v > x (exceeds our capability) or if i == j + 1 (adjacent to last robbed house)
   • Otherwise, rob this house: increment cnt and update j = i
3. Return True if cnt >= k, meaning we can rob enough houses with this capability

Binary Search Execution: The code uses bisect_left(range(max(nums) + 1), True, key=f) which:

• Searches the range [0, max(nums)]
• Looks for the leftmost (minimum) value where f(x) returns True
• This gives us the minimum capability that allows robbing at least k houses

Why This Works:

• If capability x allows robbing k houses, then any capability > x also works (monotonic property)
• Binary search efficiently finds the boundary between "not possible" and "possible"
• The greedy approach in validation is optimal because we want to maximize the count of houses robbed for a given capability, and taking any valid house early doesn't prevent us from taking more houses later

Time Complexity: O(n * log(max(nums))) where n is the length of the array Space Complexity: O(1) as we only use a few variables

Example Walkthrough

Let's walk through the solution with nums = [2, 7, 9, 3, 1] and k = 2.

Step 1: Set up binary search range

• Minimum capability: 0
• Maximum capability: max(nums) = 9
• We'll search in range [0, 9] for the minimum capability that allows robbing at least 2 houses

Step 2: Binary search process

First iteration: mid = 4

• Check if capability 4 allows robbing 2 houses
• Go through houses:
  • House 0 (value=2): 2 ≤ 4, rob it! Count = 1, last robbed index = 0
  • House 1 (value=7): 7 > 4, skip (exceeds capability)
  • House 2 (value=9): 9 > 4, skip (exceeds capability)
  • House 3 (value=3): 3 ≤ 4 and not adjacent to house 0, rob it! Count = 2
• Count = 2 ≥ k = 2 ✓
• Since it works, try smaller: search [0, 4]

Second iteration: mid = 2

• Check if capability 2 allows robbing 2 houses
• Go through houses:
  • House 0 (value=2): 2 ≤ 2, rob it! Count = 1, last robbed index = 0
  • House 1 (value=7): 7 > 2, skip (exceeds capability)
  • House 2 (value=9): 9 > 2, skip (exceeds capability)
  • House 3 (value=3): 3 > 2, skip (exceeds capability)
  • House 4 (value=1): 1 ≤ 2 and not adjacent to house 0, rob it! Count = 2
• Count = 2 ≥ k = 2 ✓
• Since it works, try smaller: search [0, 2]

Third iteration: mid = 1

• Check if capability 1 allows robbing 2 houses
• Go through houses:
  • House 0 (value=2): 2 > 1, skip (exceeds capability)
  • House 1 (value=7): 7 > 1, skip (exceeds capability)
  • House 2 (value=9): 9 > 1, skip (exceeds capability)
  • House 3 (value=3): 3 > 1, skip (exceeds capability)
  • House 4 (value=1): 1 ≤ 1, rob it! Count = 1
• Count = 1 < k = 2 ✗
• Doesn't work, need larger: search [2, 2]

Final result: minimum capability = 2

The robber can steal from houses with values [2, 1] (indices 0 and 4) with a capability of 2, which is the minimum possible capability to rob at least 2 houses.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log m)

The algorithm uses binary search on the range [0, max(nums)] to find the minimum capability. The bisect_left function performs binary search, which takes O(log m) iterations where m = max(nums). For each iteration of the binary search, the helper function f(x) is called, which iterates through all n elements of the nums array once, taking O(n) time. Therefore, the overall time complexity is O(n × log m).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space. The helper function f(x) uses two variables cnt and j to track the count and the last selected index. The binary search itself doesn't require additional space proportional to the input size. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Greedy Strategy in Validation Function

The Pitfall: A common mistake is using a different greedy strategy that seems intuitive but doesn't maximize the number of houses robbed. For example:

• Trying to minimize gaps between robbed houses
• Starting from houses with smaller values first
• Using dynamic programming instead of greedy

Wrong Approach Example:

def can_rob_k_houses_wrong(max_value):
    # Wrong: Trying to be "smart" about which houses to skip
    robbed = []
    for i, v in enumerate(nums):
        if v <= max_value:
            if not robbed or i > robbed[-1] + 1:
                robbed.append(i)
            elif len(robbed) >= 2 and i > robbed[-2] + 2:
                # Wrong logic: trying to optimize placement
                robbed[-1] = i
    return len(robbed) >= k

The Solution: Stick to the simple greedy approach: take any valid house as soon as you can. This maximizes the count because:

• Taking a house early never prevents you from taking more houses later
• Skipping a valid house might force you to skip more houses due to adjacency constraints

2. Off-by-One Error in Binary Search Range

The Pitfall: Using range(max(nums)) instead of range(max(nums) + 1) in the binary search. This would miss the case where the minimum capability equals the maximum value in the array.

Wrong Code:

# This misses the case where answer = max(nums)
return bisect_left(range(max(nums)), True, key=can_rob_k_houses)

The Solution: Always include the upper bound in the search range:

return bisect_left(range(max(nums) + 1), True, key=can_rob_k_houses)

3. Incorrect Initial Value for Last Robbed Index

The Pitfall: Initializing last_robbed_index to -1 instead of -2. This would incorrectly prevent robbing the house at index 0 when checking current_index == last_robbed_index + 1.

Wrong Code:

last_robbed_index = -1  # Wrong: 0 == (-1) + 1, so house 0 would be skipped

The Solution: Initialize to -2 or any value less than -1:

last_robbed_index = -2  # Correct: ensures house at index 0 can be robbed

4. Using bisect_right Instead of bisect_left

The Pitfall: Using bisect_right would find the rightmost position where True can be inserted, giving us a value one higher than the minimum capability.

Wrong Code:

# This returns minimum_capability + 1
return bisect_right(range(max(nums) + 1), True, key=can_rob_k_houses)

The Solution: Use bisect_left to find the leftmost (minimum) value where the condition is satisfied:

return bisect_left(range(max(nums) + 1), True, key=can_rob_k_houses)