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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

House Robber IV

Number: 2690

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, Google, Microsoft, Cashfree

Problem Description

Given an array of integers representing the amount of money in each house, determine the minimum possible "capability" (i.e., the maximum money stolen from a single house) such that the robber can rob at least k houses without robbing two adjacent houses.

Key Insights

  • The robber must avoid robbing two consecutive houses.
  • The "capability" is defined as the maximum amount taken from any robbed house.
  • We need to select at least k houses.
  • Binary search can be applied on the range of possible capabilities (from min(nums) to max(nums)).
  • A greedy method is used to determine if a given candidate capability allows robbing at least k houses.

Space and Time Complexity

Time Complexity: O(n · log(max(nums)))
Space Complexity: O(1)

Solution

We use binary search over the possible range of capabilities. For each candidate capability (mid value), apply a greedy strategy:

  1. Iterate over the houses; if a house’s money is <= candidate, count it as robbed and skip the next house.
  2. If the total count of robbed houses is at least k, the candidate is valid.
  3. Adjust the binary search boundaries based on the validity of the candidate to converge to the minimal capability.

The main idea is to narrow down the capability threshold while ensuring that the condition of robbing at least k houses without violating the adjacent rule holds.

Code Solutions

# Python solution for House Robber IV

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        # Check if it's possible to rob at least k houses with the candidate capability
        def canRob(candidate: int) -> bool:
            count, i, n = 0, 0, len(nums)
            while i < n:
                if nums[i] <= candidate:
                    count += 1     # Rob this house
                    i += 2         # Skip next house due to the adjacent rule
                else:
                    i += 1         # Move to the next house
            return count >= k

        left, right = min(nums), max(nums)
        answer = right
        # Binary search over the range of possible capabilities
        while left <= right:
            mid = (left + right) // 2
            if canRob(mid):
                answer = mid   # Found a valid candidate, try for a smaller capability
                right = mid - 1
            else:
                left = mid + 1
        return answer
← Back to All Questions