2560. House Robber IV LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2560. House Robber IV LeetCode Solution with the best time and space complexity. The solution to House Robber IV problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
House Robber IV solution in C++
House Robber IV solution in Java
House Robber IV solution in Python
Additional Resources

2560. House Robber IV LeetCode Solution image

Problem Statement of House Robber IV

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

Complexity Analysis

Time Complexity: O(\log (\max(nums) – \min(nums)))
Space Complexity: O(1)

2560. House Robber IV LeetCode Solution in C++

class Solution {
 public:
  int minCapability(vector<int>& nums, int k) {
    int l = ranges::min(nums);
    int r = ranges::max(nums);

    while (l < r) {
      const int m = (l + r) / 2;
      if (numStolenHouses(nums, m) >= k)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

 private:
  int numStolenHouses(const vector<int>& nums, int capacity) {
    int stolenHouses = 0;
    for (int i = 0; i < nums.size(); ++i)
      if (nums[i] <= capacity) {
        ++stolenHouses;
        ++i;
      }
    return stolenHouses;
  }
};
/* code provided by PROGIEZ */

2560. House Robber IV LeetCode Solution in Java

class Solution {
  public int minCapability(int[] nums, int k) {
    int l = Arrays.stream(nums).min().getAsInt();
    int r = Arrays.stream(nums).max().getAsInt();

    while (l < r) {
      final int m = (l + r) / 2;
      if (numStolenHouses(nums, m) >= k)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

  private int numStolenHouses(int[] nums, int capacity) {
    int stolenHouses = 0;
    for (int i = 0; i < nums.length; ++i)
      if (nums[i] <= capacity) {
        ++stolenHouses;
        ++i;
      }
    return stolenHouses;
  }
}
// code provided by PROGIEZ

2560. House Robber IV LeetCode Solution in Python

class Solution:
  def minCapability(self, nums: list[int], k: int) -> int:
    def numStolenHouses(capacity: int) -> int:
      stolenHouses = 0
      i = 0
      while i < len(nums):
        if nums[i] <= capacity:
          stolenHouses += 1
          i += 1
        i += 1
      return stolenHouses

    return bisect.bisect_left(range(max(nums)), k, key=numStolenHouses)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents