2560.House_Robber_IV(Medium).md

2560. House Robber IV (Medium)

Date and Time: Mar 15, 2025, 19:39 (EST)

Link: https://leetcode.com/problems/house-robber-iv

Question:

There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes.

The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed.

You are given an integer array nums representing how much money is stashed in each house. More formally, the ith house from the left has nums[i] dollars.

You are also given an integer k, representing the minimum number of houses the robber will steal from. It is always possible to steal at least k houses.

Return the minimum capability of the robber out of all the possible ways to steal at least k houses.

Example 1:

Input: nums = [2,3,5,9], k = 2
Output: 5
Explanation:
There are three ways to rob at least 2 houses:

• Rob the houses at indices 0 and 2. Capability is max(nums[0], nums[2]) = 5.
• Rob the houses at indices 0 and 3. Capability is max(nums[0], nums[3]) = 9.
• Rob the houses at indices 1 and 3. Capability is max(nums[1], nums[3]) = 9. Therefore, we return min(5, 9, 9) = 5.

Example 2:

Input: nums = [2,7,9,3,1], k = 2
Output: 2
Explanation: There are 7 ways to rob the houses. The way which leads to minimum capability is to rob the house at index 0 and 4. Return max(nums[0], nums[4]) = 2.

Constraints:

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

• 1 <= k <= (nums.length + 1)/2

Walk-through:

Run Binary Search on range [1, max(nums)], we can get the number nums[m] and use it to compare with each num in nums, to count how many houses we can rob, if counts >= k, we can update r = m, otherwise, update l = m + 1.

Python Solution:

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        # Start BS on range of rewards [1, max(nums)] to find a capability
        # Iterate nums to count how many houses <= capability, increment counts
        # If counts >= k, try to find a smaller capability by updating r = m - 1

        # TC: O(nlog(m)), n=len(nums), m=max(nums), SC: O(1)
        l, r = 1, max(nums)
        while l < r:
            m = (l+r) // 2      # capability
            # Compare nums[i] with m to count how many houses can be robbed
            i = 0
            counts = 0
            while i < len(nums):
                # If rob current house, skip the next house
                if nums[i] <= m:
                    counts += 1
                    i += 2
                else:
                    i += 1
            # Check if counts >= k and update l, r
            if counts >= k:
                r = m
            else:
                l = m + 1
        return l

Time Complexity: $O(nlog(m))$
Space Complexity: $O(1)$