House Robber II
Houses stand in a circle, and nums[i] is the amount of money in house i. You can't take from two adjacent houses, and because the street is a circle, the first and last houses are adjacent too. Return the most money you can collect.
Examples
nums = [3,4,3] returns 4
The two 3s sit at the ends of the circle, so they are neighbors. Taking the 4 alone is the best option.
nums = [2,7,9,3,1] returns 11
On a straight street, 2 + 9 + 1 = 12 would win, but the first and last houses touch. Leaving out the last house allows 2 + 9 = 11, which beats every plan that leaves out the first.
nums = [5] returns 5
A single house has no neighbors to conflict with.
Constraints
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000
Hints
Compared with the straight street, which single pair of houses creates the new conflict?
Break the circle into two straight streets: one without the last house and one without the first. Solve each with the original House Robber recurrence.
Write a helper that robs nums[lo..hi] with two rolling variables, return nums[0] when n == 1, and otherwise return max(rob(0, n - 2), rob(1, n - 1)).
Drill This: Your Approach First
Approach
The circle adds one rule: the first and last houses can't both be taken. So at least one of them is left out, and the answer is the better of two straight-line House Robber runs, one on houses 0 to n - 2 and one on houses 1 to n - 1. Each run keeps two rolling values, the best total up to the previous house and the one before it, and takes max(prev, prevPrev + nums[i]). A single house is its own answer. O(n) time, O(1) space.
Time
O(n)
Space
O(1)
Pitfall
Solutions
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
private int robRange(int[] nums, int lo, int hi) {
int prevPrev = 0, prev = 0;
for (int i = lo; i <= hi; i++) {
int cur = Math.max(prev, prevPrev + nums[i]);
prevPrev = prev;
prev = cur;
}
return prev;
}
}class Solution:
def rob(self, nums) -> int:
if len(nums) == 1:
return nums[0]
def rob_range(houses):
prev_prev = prev = 0
for money in houses:
prev_prev, prev = prev, max(prev, prev_prev + money)
return prev
return max(rob_range(nums[:-1]), rob_range(nums[1:]))