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.

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. Using Wrong Binary Search Template

The Pitfall: Using while left < right with right = mid instead of the standard template. This variant can be confusing and error-prone.

The Solution: Use the standard binary search template with while left <= right, first_true_index tracking, and right = mid - 1:

left, right = 0, max(nums)
first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

2. Incorrect Greedy Strategy in Validation Function

The Pitfall: Using a complex greedy strategy instead of the simple approach. Some might try to minimize gaps between robbed houses or use dynamic programming.

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.

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. Off-by-One Error in Binary Search Range

The Pitfall: Not including the upper bound correctly. The capability can equal the maximum value in the array.

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

right = max(nums)  # Correct: includes the maximum value