The problem
As in House Robber, but the houses stand in a circle: the first and the last are neighbours too. Return the most money you can take without robbing two neighbours.
Examples
01
- Input
nums = [2, 3, 2]
- Output
3
02
- Input
nums = [1, 2, 3, 1]
- Output
4
03
- Input
nums = [1, 2, 3]
- Output
3
Constraints
- 1 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 1000
The idea
The circle adds one rule: the first and last houses cannot both be robbed. So at least one of them is left alone.
If the last is left alone, the problem is House Robber on houses 0 to n − 2; if the first is, on houses 1 to n − 1. Solve both straight streets and take the better. (A single house is its own answer.)
- Time
- O(n) — two passes
- Space
- O(1)
Solution · every language run against every case
class Solution: def rob(self, nums: List[int]) -> int: # The first and last houses touch, so at most one of them is robbed: solve the street # without the last house and the street without the first, and take the better. def line(houses): prev2 = prev1 = 0 for x in houses: prev2, prev1 = prev1, max(prev1, prev2 + x) return prev1 if len(nums) == 1: return nums[0] return max(line(nums[:-1]), line(nums[1:]))