TL;DR
Run the linear House Robber twice — once without the last house, once without the first — and take the max. O(n) time, O(1) space.
Approach 1 — Brute-force recursion
The choice at each house is binary: rob it or skip it. Recurse over both, honoring the “no two adjacent” rule and the circle rule that houses 0 and n-1 cannot both be robbed. Decide up front whether house 0 is allowed, which fixes whether house n-1 is allowed. This splits the circular problem into two linear ones:
flowchart TD
A["Circular array nums[0..n-1]<br/>house 0 and n-1 are neighbors"] --> B["Case A: exclude last house<br/>rob_line(nums[0..n-2])"]
A --> C["Case B: exclude first house<br/>rob_line(nums[1..n-1])"]
B --> D["answer = max(Case A, Case B)"]
C --> D
Recurrence (linear, over a slice): rob(i) = max(rob(i-1), nums[i] + rob(i-2)) — skip house i, or take it and jump two back. Base: rob(<0) = 0.
def rob(nums: list[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
def rob_line(lo: int, hi: int) -> int:
# max robbery over nums[lo..hi] inclusive, no two adjacent
def rec(i: int) -> int:
if i < lo:
return 0
return max(rec(i - 1), nums[i] + rec(i - 2))
return rec(hi)
return max(rob_line(0, n - 2), rob_line(1, n - 1))
Complexity: each rec(i) fans out into two calls → O(2ⁿ) time. At n = 100 this is far too slow.
Approach 2 — Memoized top-down
rec(i) depends only on i, so there are just n distinct subproblems. Cache them.
from functools import lru_cache
def rob(nums: list[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
def rob_line(lo: int, hi: int) -> int:
@lru_cache(maxsize=None)
def rec(i: int) -> int:
if i < lo:
return 0
return max(rec(i - 1), nums[i] + rec(i - 2))
return rec(hi)
return max(rob_line(0, n - 2), rob_line(1, n - 1))
Complexity: O(n) time, O(n) space (cache + recursion stack) per line, run twice.
Approach 3 — Tabulated bottom-up
Fill dp left to right, where dp[i] is the best robbery over the slice up to house i.
def rob(nums: list[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
def rob_line(sub: list[int]) -> int:
m = len(sub)
if m == 0:
return 0
dp = [0] * m
dp[0] = sub[0]
for i in range(1, m):
take = sub[i] + (dp[i - 2] if i >= 2 else 0)
dp[i] = max(dp[i - 1], take)
return dp[-1]
return max(rob_line(nums[:-1]), rob_line(nums[1:]))
Complexity: O(n) time, O(n) space.
Approach 4 — Space-optimized (two rolling variables)
dp[i] only ever reads dp[i-1] and dp[i-2], so keep two scalars instead of the whole array.
def rob(nums: list[int]) -> int:
if len(nums) == 1:
return nums[0]
def rob_line(sub: list[int]) -> int:
prev, cur = 0, 0 # cur = best incl. house i-1, prev = best incl. i-2
for x in sub:
prev, cur = cur, max(cur, prev + x)
return cur
return max(rob_line(nums[:-1]), rob_line(nums[1:]))
Walkthrough (nums = [1,2,3,1]):
- Exclude last → line
[1,2,3]: (prev,cur) goes (0,0)→(0,1)→(1,2)→(2,4). Best 4.
- Exclude first → line
[2,3,1]: (0,0)→(0,2)→(2,3)→(3,3). Best 3.
- Answer
max(4, 3) = 4.
Complexity: O(n) time, O(1) space.
Common pitfalls
- Forgetting the
n == 1 special case: with one house there is no wrapping neighbor, and slicing off “the last house” would leave an empty list and lose the only value.
- Robbing both ends:
[5, 1, 1, 5] tempts you into 5 + 5 = 10, but houses 0 and 3 are adjacent on the circle — the real answer is 5 + 1 = 6.
- Trying to patch the linear DP with a single “did I take house 0?” flag threaded through — the two-pass split is far cleaner and provably correct.
Pattern takeaway
When a linear DP gets a wrap-around or global mutual-exclusion constraint, don’t invent a new recurrence. Fix the conflicting element two ways, solve the simpler linear problem once per case, then combine. Reducing a circular constraint to two runs of the linear solution is a reusable technique.