← DSA Atlas
Dedicated problem page · #213

House Robber II

MediumOne-Dimensional Dynamic ProgrammingHouse Robber on a circle via two linear passes1-D dynamic programming
Solve on LeetCode ↗
213
MediumOne-Dimensional Dynamic Programming1-D dynamic programmingHouse Robber on a circle via two linear passes

House Robber II

Houses are arranged in a circle, each holding some money in nums. You cannot rob two adjacent houses, and because the arrangement is circular the first and last houses are adjacent. Return the maximum amount you can rob without alerting the police.

Open official problem prompt ↗
In plain English

Maximize looted money on a circular street where no two chosen houses may be neighbors, including the wrap-around pair.

Picture it like this

Choosing non-adjacent seats around a round table: picking both seats next to the same gap is forbidden, so you plan the row twice - once ignoring the first seat, once ignoring the last.

Example
Input
nums = [2, 3, 2]
Output
3
Why
Robbing house 0 and house 2 is illegal (they are adjacent on the circle), so the best single choice is house 1 with 3.
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 1000
Pattern lesson

See the pattern, then code

House Robber on a circle via two linear passes
Recognition clue

It is the linear House Robber but the ends wrap around - the circular adjacency constraint is the tell to solve two linear subproblems.

↗
One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. Since the first and last houses cannot both be robbed, the optimum either excludes the first house or excludes the last; run the linear robber on nums[1:] and on nums[:-1] and take the larger.

New words, made simpleKnow these before the algorithm
Circular adjacency
The constraint that index 0 and index n-1 are neighbors.
prev1 / prev2
Best totals for the previous and previous-previous house in a linear pass.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Naive subset search

Exponential and unnecessary.

Try all independent sets of houses.

Time O(2^n)Space O(n)
Best choiceTwo linear DP passes

Reduces the circular problem to two solved subproblems.

Break the circle by excluding either the first or the last house, solve each linearly, take the max.

Time O(n)Space O(1)
The rule we keep true

Invariant

Within each linear pass, prev1 is the maximum robbable amount considering all houses seen so far.

Why this is correct

Reasoning

Any valid circular selection omits the first house, the last house, or both; the pass over nums[1:] covers selections without the first and the pass over nums[:-1] covers those without the last, and their maximum dominates the both-omitted case too.

The algorithm in three movesSay these aloud before coding
1Handle the single-house case directly

exclude last -> rob([2,3]) = 3

2Define a linear robber that folds max(prev1, prev2 + x)

exclude first -> rob([3,2]) = 3

3Run it on nums without the last house

answer = max(3,3) = 3

4Run it on nums without the first house

5Return the maximum of the two runs

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
20
31
22
1 · Readlen=3
2 · AskOne house only?
3 · Update stateno
4 · ResultProceed to two passes.
Key takeaway

House 1 alone yields 3; robbing both ends is blocked by the circular link.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Single-house guard

    With one house there is no slicing to do; slices like nums[1:] would be empty.

  2. 2
    Lines 6-10Linear robber

    Classic O(1) fold: each house is either skipped (prev1) or taken with the amount two back (prev2 + x).

  3. 3
    Lines 12Break the circle

    Take the better of excluding the first or the last house to honor the wrap-around constraint.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single house returns its value
  • Two houses returns the larger of the two
  • All zeros returns 0
  • Large adjacent values where skipping ends matters
!

Common beginner mistakes

  • Running the plain linear robber and forgetting the wrap-around
  • Not special-casing length 1, which makes both slices empty and returns 0 incorrectly
  • Double-counting a house by considering both ends in one pass
Check your understanding

Why is taking the max of the two passes enough, when neither pass explicitly forbids robbing both ends?

More in One-Dimensional Dynamic Programming

#198House RobberTake-or-skip linear DP#322Coin ChangeUnbounded knapsack (min coins)#300Longest Increasing SubsequencePatience sorting (tails array)#5Longest Palindromic SubstringExpand around center#32Longest Valid ParenthesesIndex stack with sentinel base#70Climbing StairsFibonacci-style linear DP