House Robber IV

main.md

Question

Approach

For this question, I used a binary search approach to determine the minimum capability the robber needs. The search space is between the smallest and largest house values.

The helper function canRob(capability) checks if it's possible to rob at least k houses without stealing from adjacent ones.

Implementation

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        left, right = min(nums), max(nums)
        
        def canRob(capability: int) -> bool:
            count, i = 0, 0
            while i < len(nums):
                if nums[i] <= capability:
                    count += 1
                    i += 1
                i += 1
            return count >= k
        
        while left < right:
            mid = (left + right) // 2
            if canRob(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

Complexities

• Time: O(n log max(nums))
• Space: O(1)