Problem overview
rob receives a list nums: house i holds nums[i] money. The houses stand in a circle, so the last house is a neighbour of house 0. Robbing two neighbouring houses sets off the alarm. The function returns the most money that can be robbed without robbing two neighbours.
It is the straight-street House Robber with one extra rule: the first and the last house cannot both be robbed.
For nums = [2, 3, 2] the answer is 3. Houses 0 and 2 hold 2 each but are neighbours in the circle, so the best plan is house 1 alone. For [1, 2, 3, 1] the answer is 4, from houses 0 and 2. For [400, 0, 0, 400, 0, 0, 400] the answer is 800: on a street with two ends, houses 0, 3 and 6 would give 1200 (the helper below returns exactly that for the whole list), but in the circle only two of them can be taken.
Approach: break the circle into two streets
Every valid plan leaves out house 0 or leaves out the last house (or both). So the circle can be cut in two ways:
- Houses
0ton - 2: the last house is ignored, so these form a street with two ends. - Houses
1ton - 1: the first house is ignored, again a street with two ends.
The best plan overall is the better of the two results. A plan that robs neither end is counted in both, which does no harm because only the maximum is needed. Each street is the ordinary House Robber problem, solved with two running totals.
The street rule is: standing at house i, the best total up to it is the larger of two choices. Skip it and keep the best for the houses before it, curr. Or rob it, which means house i - 1 must stay untouched, so its money adds to the best total from two houses back, prev. Two variables are enough, so the extra space is constant.
On the houses 0 to 5 of the third example (the street without the last house), the totals go:
i=0 money=400 best=400
i=1 money=0 best=400
i=2 money=0 best=400
i=3 money=400 best=800
i=4 money=0 best=800
i=5 money=0 best=800
House 6 is left out of this street, so its 400 never counts, and the street gives 800.
Step by step
- Store the number of houses in
n = len(nums). - Handle one house. If
n == 1, returnnums[0]. A lone house has no neighbour, and both cuts below would leave nothing. - Leave out the last house. Rob houses 0 to
n - 2with the helperself.robRange(nums, 0, n - 2)and store the result inwithoutLast. The helper is written afterwards, which keepsrobshort. - Leave out the first house. Do the same for houses 1 to
n - 1, stored inwithoutFirst. - Return the larger of the two with
max. - Declare the helper
robRange(self, nums, start, end). It returns the most money from housesstarttoendon a street with two ends. - Start
prevat 0: the best total from the houses up to two before the current one. - Start
currat 0: the best total up to the house just before the current one. Before the first house of the range nothing has been robbed. - Loop with
for i in range(start, end + 1). The stop ofrangeis excluded, soend + 1includes houseend. - Compute the best total up to house
i:best = max(curr, prev + nums[i]). - Shift the totals:
prev = currfirst, thencurr = best. The order matters: changingcurrfirst would lose the valueprevneeds. - Return
currafter the loop. It is the best total for the whole range.
The solution in Python
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
withoutLast = self.robRange(nums, 0, n - 2)
withoutFirst = self.robRange(nums, 1, n - 1)
return max(withoutLast, withoutFirst)
def robRange(self, nums: List[int], start: int, end: int) -> int:
prev = 0
curr = 0
for i in range(start, end + 1):
best = max(curr, prev + nums[i])
prev = curr
curr = best
return curr
Python details worth a closer look:
range(start, end + 1).rangestops before its second argument. When the range is empty, as inrange(1, 1), the loop body never runs androbRangereturns 0.- Helpers on the same object.
robRangeis called asself.robRange(...). It is defined belowrob, which is fine, because Python looks the method up only whenrobruns. - The list is not copied. The helper receives the same
numsplus two indices. Slicing instead (nums[:-1],nums[1:]) also works, but it makes two new lists. - The type hints (
List[int],-> int) document the code and don't change how it runs.
Complexity
Time: O(n). Each call to robRange loops over at most n - 1 houses with constant work per house, and rob makes two calls.
Space: O(1). Only a few integers are kept: prev, curr and best.
Edge cases and common mistakes
- One house.
[5]returns 5. Without the early return, the calls would use the ranges 0 to -1 and 1 to 0, which are empty, and the result would be 0. - Two houses. They are neighbours, so only one can be robbed:
[2, 7]returns 7. The two streets are the single houses 0 and 1. - Solving the straight street. Running the plain House Robber over the whole list gives 1200 for the third example, which is more than the circle allows.
- Keeping only one cut. Dropping only the last house misses plans that need it: for
[1, 2, 3]the best plan is house 2 alone (3), but houses 0 and 1 give only 2. - Updating in the wrong order. Setting
curr = bestbeforeprev = currmakesprevequal to the new total, so a robbed house gets added to its own neighbour's money. - Zeros. Houses may hold 0 money. Nothing special is needed:
maxhandles them, and[0]returns 0.
Testing
[2, 3, 2]gives 3.[1, 2, 3, 1]gives 4.[400, 0, 0, 400, 0, 0, 400]gives 800.[5]gives 5.[2, 7]gives 7.[1, 2, 3]gives 3.[4, 1, 1, 4]gives 5: the two 4s are neighbours in the circle, so it is a 4 and a 1.
