⚡Flashcard Drill➔
NeetCode #279LC-2560MediumBinary Search
← Back to All Problems

#279 · #2560 · House Robber IV(打家劫舍 IV)

📌 Problem Statement & Constraints

You are given an integer array nums and an integer k. You must rob at least k houses; adjacent houses cannot both be robbed. The capability is the maximum amount robbed from any single house. Return the minimum possible capability. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9, 1 <= k <= (nums.length + 1) / 2.

💡 Core Algorithmic Approaches

  1. Binary search on the capability c: "can we rob at least k houses using only houses with nums[i] <= c" is monotone.
  2. The greedy for a given c is to scan left to right and rob any eligible house, skipping the next one -- this maximises the count.
  3. The eligibility is nums[i] <= c, and adjacency is handled by jumping two steps after a robbery.
  4. The lower bound is min(nums) and the upper bound max(nums), since k is guaranteed achievable.

💻 Benchmark Python3 Implementation

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        lo, hi = min(nums), max(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            # greedily count how many non-adjacent houses have value <= mid
            cnt = 0
            i = 0
            while i < len(nums):
                if nums[i] <= mid:
                    cnt += 1
                    i += 2             # cannot rob the neighbour
                else:
                    i += 1
            if cnt >= k:
                hi = mid               # feasible -> try a lower capability
            else:
                lo = mid + 1
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log(max(nums))): each greedy pass is O(n).
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using DP to count the maximum robberies: O(n) per check, which is the same, but the greedy is simpler and provably optimal for counting.
  • Jumping only one step after robbing: the next house cannot be robbed, so the jump is two.
  • Setting the lower bound to 0: a capability below min(nums) can never rob even one house, so min(nums) is tight.
  • Using hi = mid - 1 when feasible: could skip the optimum.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems