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 <= 1051 <= nums[i] <= 1091 <= k <= (nums.length + 1)/2This approach uses dynamic programming to solve the problem. We define a DP array where dp[i] represents the minimum capability needed to rob at least k houses up to index i. We'll build this array by considering two choices: either rob the current house or skip it. Our goal is to find the minimum capability where k houses can be robbed without robbing adjacent houses.
This code initializes a DP array and updates it by iterating over the houses, deciding whether to rob or not at each step. Given the constraints, it finds the minimum possible maximum capability to rob at least k houses.
Java
Time Complexity: O(n), Space Complexity: O(n)
This approach involves using binary search on the potential capability range and verifying the capability using a sliding window technique. The basic idea is to efficiently determine if it’s possible to rob at least k houses with a given capability, adjusting the capability through binary search.
This JavaScript solution first defines a helper function that checks the feasibility of robbing at least k houses with a given capability using a sliding window. Binary search adjusts the capability range to find the minimum.
C++
Time Complexity: O(n log m), where m is the range of money, Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), Space Complexity: O(n) |
| Binary Search with Sliding Window | Time Complexity: O(n log m), where m is the range of money, Space Complexity: O(1) |
House Robber - Leetcode 198 - Python Dynamic Programming • NeetCode • 377,825 views views
Watch 9 more video solutions →Practice House Robber IV with our built-in code editor and test cases.
Practice on FleetCode