LeetCode 2560 - House Robber IV

The problem describes a scenario where a robber wants to steal from houses lined along a street, but with the constraint that adjacent houses cannot both be robbed.

leetcodemediumarraybinary-searchdynamic-programminggreedy

LeetCode Problem 2560

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Dynamic Programming, Greedy

Solution

Problem Understanding

The problem describes a scenario where a robber wants to steal from houses lined along a street, but with the constraint that adjacent houses cannot both be robbed. Each house has a certain amount of money, represented as an array nums, and the robber wants to steal from at least k houses. Importantly, the robber’s capability is defined as the maximum amount of money stolen from a single house among all the houses robbed. The goal is to minimize this capability across all valid ways of robbing at least k houses.

The input nums is an integer array with 1 <= nums.length <= 10^5 and 1 <= nums[i] <= 10^9. The value k satisfies 1 <= k <= (nums.length + 1) / 2. These constraints indicate that a brute-force solution that checks all possible combinations is infeasible due to the exponential number of subsets. The problem guarantees that it is always possible to steal at least k houses.

Edge cases include scenarios with the minimum number of houses, houses with identical values, or when k is exactly half the number of houses, which may force picking every other house.

Approaches

The brute-force approach would involve generating all subsets of houses that are non-adjacent, counting how many houses are robbed, and then calculating the capability for each subset. While this guarantees correctness, its complexity is O(2^n), which is infeasible for n up to 10^5.

The key insight is that the problem reduces to a decision problem: for a given maximum capability x, can we select at least k houses such that no two are adjacent and every selected house has value <= x? If we can, then x is a feasible capability. Using this insight, we can apply binary search on the capability. For a given mid value in binary search, we can iterate through the array greedily to count the maximum number of houses that can be robbed without violating adjacency. If we can reach k, we try a smaller mid; otherwise, we increase mid.

This transforms the problem into binary search + greedy selection, which is much more efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Check all non-adjacent subsets, infeasible for large n
Binary Search + Greedy O(n log(max(nums))) O(1) Binary search on capability, greedy check for feasibility

Algorithm Walkthrough

  1. Initialize binary search bounds: low = min(nums) and high = max(nums). These represent the smallest and largest possible capabilities.
  2. While low < high, calculate mid = (low + high) // 2.
  3. Check if it is possible to rob at least k houses with capability mid using a greedy approach:
  • Iterate through nums.
  • Maintain a counter count for houses robbed.
  • If the current house has value <= mid, rob it and skip the next house (to respect the adjacency rule), incrementing count.
  1. If count >= k, it means mid is a feasible capability. Update high = mid to try a smaller value.
  2. If count < k, mid is too small. Update low = mid + 1.
  3. Once low >= high, low is the minimum capability required.

Why it works: The greedy check guarantees that we maximize the number of houses robbed under a given mid because we take every eligible house sequentially and skip the next to respect adjacency. The binary search ensures that we find the smallest feasible mid efficiently.

Python Solution

from typing import List

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        def can_rob_with_cap(cap: int) -> bool:
            count = 0
            i = 0
            n = len(nums)
            while i < n:
                if nums[i] <= cap:
                    count += 1
                    i += 2  # skip next house
                else:
                    i += 1
            return count >= k
        
        low, high = min(nums), max(nums)
        while low < high:
            mid = (low + high) // 2
            if can_rob_with_cap(mid):
                high = mid
            else:
                low = mid + 1
        return low

Implementation walkthrough: The function can_rob_with_cap iterates greedily through the houses, counting how many can be robbed if each robbed house must not exceed cap. The binary search adjusts low and high based on whether mid is feasible. When the loop ends, low represents the minimum capability.

Go Solution

func minCapability(nums []int, k int) int {
    canRob := func(cap int) bool {
        count := 0
        i := 0
        n := len(nums)
        for i < n {
            if nums[i] <= cap {
                count++
                i += 2
            } else {
                i++
            }
        }
        return count >= k
    }

    low, high := nums[0], nums[0]
    for _, val := range nums {
        if val < low {
            low = val
        }
        if val > high {
            high = val
        }
    }

    for low < high {
        mid := (low + high) / 2
        if canRob(mid) {
            high = mid
        } else {
            low = mid + 1
        }
    }
    return low
}

Go-specific notes: We explicitly calculate low and high instead of using min/max functions. Slice iteration is used instead of indexing with range. Otherwise, the logic mirrors Python.

Worked Examples

Example 1: nums = [2,3,5,9], k = 2

Step mid count decision
Binary search range 2-9 - Initialize low=2, high=9
mid=5 - 2 can rob houses 0 and 2
mid feasible high=5 - Continue search
low >= high 5 - Result is 5

Example 2: nums = [2,7,9,3,1], k = 2

Step mid count decision
Binary search range 1-9 - Initialize low=1, high=9
mid=5 - 2 Can rob houses 0 and 4
mid feasible high=5 - Continue search
mid=3 - 2 Can rob houses 0 and 4
mid feasible high=3 - Continue search
mid=2 - 2 Can rob houses 0 and 4
mid feasible high=2 - low=2
low >= high 2 - Result is 2

Complexity Analysis

Measure Complexity Explanation
Time O(n log(max(nums))) Binary search over capability range, with O(n) greedy check each time
Space O(1) Constant extra space; no additional data structures proportional to input

The algorithm is efficient for the input size up to 10^5, as the binary search only needs log(max(nums)) iterations, and each iteration processes the array linearly.

Test Cases

# Provided examples
assert Solution().minCapability([2,3,5,9], 2) == 5  # Minimum capability from example 1
assert Solution().minCapability([2,7,9,3,1], 2) == 2  # Minimum capability from example 2

# Edge cases
assert Solution().minCapability([1], 1) == 1  # Only one house, must pick it
assert Solution().minCapability([1,1,1,1,1], 3) == 1  # All houses same value
assert Solution().minCapability([5,1,5,1,5], 2) == 1  # Alternating high/low values
assert Solution().minCapability([10**9]*100000, 50000) == 10**9  # Large n and max nums
assert Solution().minCapability([1,2,3,4,5,6], 3) == 3  # Minimum capability requires skipping some large numbers
Test Why
[2,3,5,9], 2 Provided example
[2,7,9,3,1], 2 Provided example
[1], 1 Single house edge case
[1,1,1,1,1], 3 All identical house values
[5,1,5,1,5], 2 Skipping alternating high values
[10^9 repeated 100k times], 50k Stress test with large n and values
[1,2,3,4,5,6], 3 Minimum capability with multiple