Example 1
ready- Input
nums = [ 2, 3, 2 ]- Expected
3- Why
- the two 2s are neighbors around the circle, so take 3
House Robber II
35 min · rob()mediumOpen in LeetCode #213 ↗
Closing the street into a circle turns its two safest-looking ends into neighbors.
The array nums lists the cash in houses arranged around a circle. You can't rob two
adjacent houses, meaning neighboring positions on that circle. In particular, the
first and last houses are adjacent. Return the largest total you can collect without
choosing an adjacent pair.
You may skip any house, every amount is non-negative, and a single-house circle lets you take that one house.
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 1_000
Hints
Break the circle somewhere
A valid plan can never contain both the first and last houses. Split all plans into those that exclude the first and those that exclude the last.
Reuse the straight-street answer
Each split leaves one ordinary linear range. Solve 0..n-2 and 1..n-1, then
keep the larger result.
Protect the one-house case
With one house, those two ranges would be empty or overlap awkwardly. Return its value before running either linear pass.
Follow-up
If the houses formed a branching neighborhood instead of one circle, what would a state need to remember about each house's parent?
Visible cases
Examples
Example 2
ready- Input
nums = [ 1, 2, 3, 1 ]- Expected
4- Why
- houses 0 and 2 contribute 1 + 3
Example 3
ready- Input
nums = [ 1 ]- Expected
1- Why
- a one-house circle has no second house to conflict with
Interview signal
Asked at
AmazonGoogle
Two recursive streets
The circular rule says the first and last houses can't both be chosen. Enumerate two complete worlds:
- allow the first house but exclude the last, and
- exclude the first house but allow the last.
Within either range, recursively take or skip each house.
def rob(nums: list[int]) -> int:
if len(nums) == 1:
return nums[0]
def best_in_range(i: int, end: int) -> int:
if i > end:
return 0
skip = best_in_range(i + 1, end)
take = nums[i] + best_in_range(i + 2, end)
return max(skip, take)
exclude_last = best_in_range(0, len(nums) - 2)
exclude_first = best_in_range(1, len(nums) - 1)
return max(exclude_last, exclude_first)Every valid plan appears in at least one world, but repeated suffixes make each recursive search exponential.
Time O(2ⁿ). Space O(n) for the recursion stack.
Two rolling DP passes
Dynamic programming (DP) reuses answers to smaller subproblems. For any chosen linear range, name its three pieces:
- State:
dp[k]is the best total from the firstkhouses in that range. - Transition:
dp[k] = max(dp[k - 1], dp[k - 2] + cash); skip the newest house or take it with the best total from two positions back. - Base case: an empty range has total
0, while a one-house range has that house's value.
The transition needs only two earlier answers, so the linear helper uses rolling variables. Run it once while excluding each end.
def rob(nums: list[int]) -> int:
if len(nums) == 1:
return nums[0]
def best_line(start: int, end: int) -> int:
two_houses_back = 0
one_house_back = 0
for i in range(start, end + 1):
current = max(one_house_back, two_houses_back + nums[i])
two_houses_back = one_house_back
one_house_back = current
return one_house_back
exclude_last = best_line(0, len(nums) - 2)
exclude_first = best_line(1, len(nums) - 1)
return max(exclude_last, exclude_first)The split is exhaustive because every valid plan excludes at least one endpoint. Taking the better of the two linear optima therefore keeps the best circular plan.
Time O(n). Space O(1).
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
3
Run: visible + custom · Submit: full suite