DSA AnimatorDSA animations
House Robber II LC #213 Medium Circular DP
Problem

Same as House Robber but houses are arranged in a circle. First and last are adjacent. Return max money without alerting.

Approach
Run House Robber twice: (1) skip last house, (2) skip first house. Take max.
Try Examples
Approach
Two Passes — Break the Circle
Pass 1: houses [0..n-2] (skip last). Pass 2: houses [1..n-1] (skip first). Return max of both.
Two Passes
Load an example.
Variables
Pass 1
—
Pass 2
—
Result
—
Step Logic
Press ▶ Play or Next Step to begin.
💰
Ready
0 / 0
Select an example.
Algorithm
1
robRange(nums, 0, n-2) — skip last
2
robRange(nums, 1, n-1) — skip first
3
return max(pass1, pass2)
Time
O(n)
Space
O(1)
Why This Works

In a circle, we can't rob both first and last. So the optimal is either: best excluding last, or best excluding first. These two linear subproblems cover all valid solutions.

How to solve House Robber II

LeetCode 213 · Medium · Dynamic Programming · Pattern: Circular 1D DP

Why the obvious approach is slow

Trying every subset of houses that are not adjacent is exponential. The circle is the only new difficulty compared with House Robber 1.

The key idea

The first and the last house can never both be robbed. So solve two straight line problems. One skips the last house, and the other skips the first house. For each line, use the House Robber rule: the best up to house i is the larger of skipping it, or robbing it plus the best up to i minus 2. The answer is the larger of the two results.

Remember

Break a circle by solving two lines, each excluding one end. Then reuse the linear solution.

Run the animation above on your own input, or watch the 1:43 video explanation of House Robber II with a dry run and Java code.

More Dynamic Programming problems