We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

House Robber IV

Difficulty: Medium

Problem Description

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 i-th 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.

Key Insights

  • The robber cannot rob two adjacent houses.
  • The goal is to minimize the maximum amount of money stolen from the houses robbed.
  • A binary search can be employed on the possible maximum capability values to efficiently find the minimum achievable capability while satisfying the robbery constraints.

Space and Time Complexity

Time Complexity: O(n log(max)) where n is the number of houses and max is the highest value in the nums array.
Space Complexity: O(1) since we are using a constant amount of extra space.

Solution

To solve this problem, we can utilize a binary search approach on the capability values (maximum amount of money stolen) while iterating through the houses to check if it’s possible to rob at least k houses without exceeding the current capability.

  1. Define the search range for the capability as [min(nums), max(nums)].
  2. For each mid value in the binary search:
    • Iterate through the houses and count how many can be robbed without exceeding the mid capability and avoiding adjacent houses.
    • If the count is at least k, then it is possible to rob with this capability, and we try for a smaller capability. Otherwise, we increase the capability.
  3. Continue this until we find the minimum possible capability that allows robbing at least k houses.

Code Solutions

def minCapability(nums, k):
    def canRobWithCapability(capability):
        count = 0
        i = 0
        while i < len(nums):
            if nums[i] <= capability:
                count += 1
                i += 2  # Skip the next house
            else:
                i += 1
        return count >= k

    left, right = min(nums), max(nums)
    while left < right:
        mid = (left + right) // 2
        if canRobWithCapability(mid):
            right = mid  # Try for a smaller capability
        else:
            left = mid + 1  # Increase capability
    return left
← Back to All Questions