The only thing the circle changes is that house 0 and house n-1 can no longer both be robbed. So any valid plan either excludes house 0 or excludes house n-1 (or both) – it can never need both restrictions at once, so checking those two cases separately and taking the max covers every possibility. Each case is then a plain non-circular House Robber on a slice of the array.
Brute Force Recursion
Time O(2ⁿ)Space O(n)Reuse the linear House Robber recursion on two slices: houses 0..n-2 (excluding the last house) and houses 1..n-1 (excluding the first house). The better of the two is the answer.
class Solution: def rob(self, nums: list[int]) -> int: def robLine(houses: list[int]) -> int: def helper(i: int) -> int: if i < 0: return 0 return max(helper(i - 1), helper(i - 2) + houses[i]) return helper(len(houses) - 1)
n = len(nums) if n == 1: return nums[0] return max(robLine(nums[:-1]), robLine(nums[1:]))Each robLine call is the exponential House Robber recursion, run twice → still O(2ⁿ) time, O(n) recursion depth.
Bottom-Up DP
OptimalTime O(n)Space O(n)Run the linear House Robber DP on nums[0:n-1] and on nums[1:n], and take the larger result. Each linear pass fills dp[i] = max(dp[i-1], dp[i-2] + houses[i]) left to right.
class Solution: def rob(self, nums: list[int]) -> int: def robLine(houses: list[int]) -> int: prev2, prev1 = 0, 0 for money in houses: prev2, prev1 = prev1, max(prev1, prev2 + money) return prev1
n = len(nums) if n == 1: return nums[0] return max(robLine(nums[:-1]), robLine(nums[1:]))Watch both linear passes on nums = [1, 2, 3, 1] — skip the last house, then skip the first — and how each rolling pass decides to take or skip a house.
Street (first and last are neighbours)
Rolling DP
Two linear cases
Circle split: case 1 skips the last house and solves the linear street [1, 2, 3].
This pass (excluding house index 3) yields 4. Excluding house index 0 instead gives houses [2, 3, 1], whose best is 3. max(4, 3) = 4, matching the expected answer.
Each linear pass is O(n) time, O(1) space with rolling variables (shown here as a small full array for clarity); running it twice keeps the overall complexity at O(n) time, O(1) space.