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
- Binary search on the capability
c: "can we rob at leastkhouses using only houses withnums[i] <= c" is monotone. - The greedy for a given
cis to scan left to right and rob any eligible house, skipping the next one -- this maximises the count. - The eligibility is
nums[i] <= c, and adjacency is handled by jumping two steps after a robbery. - The lower bound is
min(nums)and the upper boundmax(nums), sincekis 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, somin(nums)is tight. - Using
hi = mid - 1when 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.