Same rules as House Robber, but the houses are arranged in a circle — house 0 and the last house are now neighbors too. Return the most money you can rob without robbing two adjacent houses.
Example
Input nums = [2,3,2]
Output 3
Key Pointers
The circular constraint only ever matters because house 0 and house n-1 can't both be robbed — everything else is identical to the linear House Robber problem.
Split into two linear subproblems: "rob houses 0..n-2" and "rob houses 1..n-1". At most one of house 0 / house n-1 can appear in any valid robbery, so the true answer is the max of the two.
A single-house input needs its own direct check, since excluding either end of a one-element range would leave nothing to rob from.
Step-by-Step Analysis
If there's only one house, return its value directly.
Run the linear House Robber logic on every house except the last.
Run the same linear logic on every house except the first.
Return the larger of the two results.
Complexity
Time: O(n) — Space: O(1)
Code
def rob(nums: list[int]) -> int:
if len(nums) == 1:
return nums[0]
def rob_linear(houses: list[int]) -> int:
rob1, rob2 = 0, 0
for n in houses:
rob1, rob2 = rob2, max(n + rob1, rob2)
return rob2
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
Code Explanation
How the solution above works, piece by piece.
A single house: just rob it.
rob_linear is the House Robber solution for a straight street.
The circle only adds one constraint: house 0 and house n−1 can't both be robbed. Every valid plan therefore avoids at least one of them.
So the answer is the better of rob_linear(nums[:-1]) (never rob the last) and rob_linear(nums[1:]) (never rob the first).
Two linear passes: O(n) time; the slices use O(n) space (index bounds would make it O(1)).
Visual Walkthrough
Running it on nums = [2, 3, 2]:
Because the first and last houses touch, they can't both be robbed. So solve two ordinary House Robber problems, one without the last house and one without the first, and take the better. Here both give 3 (rob the middle house).