Problem Informations

• Problem Index: 2560
• Problem Link: House Robber IV
• Topics: Array, Binary Search

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.

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 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^9$
• $1 \leq k \leq (nums.length + 1)/2$

Intuition

The problem at hand is a classical example of optimizing a resource under constraints, where the goal is to maximize the income of robberies with a condition to skip adjacent houses. The problem further requires that the minimum capability, defined as the maximum amount of money stolen from any one house, is optimized. An attractive option to find this optimal capability is using a binary search approach on the “capability” value since we are checking for a threshold.

The complexity arises from needing to choose at least k non-adjacent houses in such a way that the capability is minimal. The binary search idea is utilized here not in the conventional sense of finding a specific value, but rather finding the minimum feasible capability.

Approach

The solution can be broken down into two main components: a helper function check to verify if a given capability is feasible, and a binary search mechanism to determine the minimum possible capability.

1. Helper Function check:

   • This function verifies if it is possible to rob at least k houses such that the maximum money taken from any house does not exceed a given test capability.
   • The function iterates over each house and checks if the money in the house is less than or equal to test. If true, it considers this house “robbed,” decreases the count k, and skips the adjacent house.
   • The process continues until we’ve either successfully planned to rob k houses or run out of houses, confirming whether test capability is sufficient.

2. Binary Search for Minimum Capability:

   • The approach efficiently narrows down the minimum capability by employing a form of binary-like search.
   • Initialize ans to -1, marking it as a starting point.
   • Use the maximum value in nums as the starting jump step for binary-like search since no capability needs to exceed the largest stash in a house.
   • Iteratively reduce this jump by dividing it by 2, analogous to halving the search space in a traditional binary search.
   • For each value that ans + jump can take, verify using the check function if it’s feasible to rob k houses under this capability. If not feasible, increase ans by jump.
   • The search ends when jumps are reduced to 0, ensuring that ans + 1 provides the smallest sufficient capability.

This method efficiently trades off time complexity, utilizing the linear scan in check with a logarithmic adjustment in minCapability, resulting in an overall time complexity driven by $O(n \log m)$, where $n$ is the number of houses and $m$ is the maximum money value.

Code

C++

class Solution {
public:
    // Function to check if it's possible to rob at least `k` houses
    // with the robber's capability being less than or equal to `test`.
    bool check(vector<int>& nums, int k, int test) {
        // Iterate through the houses.
        for (int i = 0; i < nums.size(); i++) {
            // If the current house can be robbed within the given capability.
            if (nums[i] <= test) {
                k--; // Decrease the count of houses needed to be robbed.
                i++; // Skip the adjacent house.
            }
        }
        // Return true if at least `k` houses can be robbed.
        return (k <= 0);
    }

    // Function to determine the minimum capability required to rob at least `k` houses.
    int minCapability(vector<int>& nums, int k) {
        int ans = -1; // Initialize the answer variable.

        // Use a binary search-like approach to find the minimum capability.
        for (int jump = *max_element(nums.begin(), nums.end()); jump > 0; jump >>= 1) {
            // Try to find if it's possible with the current `ans + jump`.
            while (!check(nums, k, ans + jump)) {
                ans += jump; // Increase the capability.
            }
        }

        // The result is incremented by 1 to get the correct minimum capability.
        return ans + 1;
    }
};

Python

class Solution:
    # Function to check if it's possible to rob at least `k` houses
    # with the robber's capability being less than or equal to `test`.
    def check(self, nums, k, test):
        # Iterate through the houses.
        i = 0
        while i < len(nums):
            # If the current house can be robbed within the given capability.
            if nums[i] <= test:
                k -= 1  # Decrease the count of houses needed to be robbed.
                i += 1  # Skip the adjacent house.
            i += 1
        # Return true if at least `k` houses can be robbed.
        return k <= 0

    # Function to determine the minimum capability required to rob at least `k` houses.
    def minCapability(self, nums, k):
        ans = -1  # Initialize the answer variable.

        # Use a binary search-like approach to find the minimum capability.
        jump = max(nums)
        while jump > 0:
            # Try to find if it's possible with the current `ans + jump`.
            while not self.check(nums, k, ans + jump):
                ans += jump  # Increase the capability.
            jump >>= 1

        # The result is incremented by 1 to get the correct minimum capability.
        return ans + 1

Complexity

• Time complexity: The time complexity for the function minCapability is $O(n \log M)$, where $n$ is the length of nums and $M$ is the maximum value in nums. The reason is as follows:

  • The outer loop in minCapability performs a binary search over the range of possible capabilities, which is $O(\log M)$ iterations.

  • Within each iteration of the binary search, the check function is called, which has a linear time complexity of $O(n)$ because it iterates through the entire list nums once.

  Therefore, the overall time complexity is the product of these two factors: $O(n \log M)$.

• Space complexity: The space complexity is $O(1)$, as the algorithm uses only a constant amount of additional space regardless of the input size. The only additional storage used is for a few integer variables, which does not depend on the size of nums or k. The manipulations and checks are done in-place, without requiring any extra space proportional to the input size.