Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3

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 <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= (nums.length + 1)/2

Similar Problems

House Robber House Robber 2 - Houses in circle House Robber 3 - Houses in Binary Tree

Solution

Method 1 - Greedy

To solve this problem effectively, we need to determine the minimum possible capability of the robber such that he can steal from at least k houses, while respecting the condition of not robbing two adjacent houses.

Approach

  1. Binary Search on Capability:
    • The idea is to use binary search to find the minimum “capability” (cap). Here, cap represents the maximum amount the robber steals in a single house across all the selected houses.
    • For a given capability, we check if it is feasible to rob at least k houses:
      • To check feasibility, we utilise a greedy approach where we simulate robbing each house only if the amount in that house is ≤ cap, without selecting adjacent houses.
  2. Key Functionality - Feasibility Check:
    • Traverse the houses sequentially and greedily select houses to rob as long as the amount in the house (nums[i]) is ≤ cap.
    • If the robber can rob at least k houses in this manner, then that capability is feasible.
  3. Binary Search Execution:
    • Use binary search to find the minimum feasible cap:
      • Start with low = min(nums) (the smallest amount in any house) and high = max(nums) (the largest amount in any house).
      • For each mid-point in the binary search, check if it’s feasible to rob k houses with that capability.
      • Narrow the search range accordingly.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    public int minCapability(int[] nums, int k) {
        int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;
        for (int n : nums) {
            low = Math.min(low, n);
            high = Math.max(high, n);
        }

        int ans = high;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canRob(nums, k, mid)) {
                ans = mid; // Update answer if feasible
                high = mid - 1; // Try for a smaller capability
            } else {
                low = mid + 1; // Try for a larger capability
            }
        }
        return ans;
    }

    private boolean canRob(int[] nums, int k, int cap) {
        int count = 0, i = 0;
        while (i < nums.length) {
            if (nums[i] <= cap) {
                count++;
                i += 2; // Skip the next house
            } else {
                i++;
            }
            if (count >= k) return true; // If at least k houses are robbed
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        def can_rob(cap: int) -> bool:
            count, i = 0, 0
            while i < len(nums):
                if nums[i] <= cap:
                    count += 1
                    i += 2  # Skip the next house
                else:
                    i += 1
                if count >= k:
                    return True
            return False

        low, high = min(nums), max(nums)
        ans = high
        while low <= high:
            mid = (low + high) // 2
            if can_rob(mid):
                ans = mid  # Update answer if feasible
                high = mid - 1  # Try for a smaller capability
            else:
                low = mid + 1  # Try for a larger capability
        return ans

Complexity

  • ⏰ Time complexity: O(n * log(max(nums)))
    • Binary search runs in O(log(max(nums))).
    • Feasibility check performed in each binary search step costs O(n).
    • Total time complexity: O(n * log(max(nums))).
  • 🧺 Space complexity: O(1) since no additional data structures are used.