Dynamic Programming · LC #213
House Robber II
Extends House Robber to a circular arrangement by running the linear algorithm twice - once excluding the last house and once excluding the first - then taking the maximum.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Houses are arranged in a circle. You cannot rob adjacent houses, and the first and last are adjacent. Maximise total money robbed.
Sample I/O
Input: nums = [2,3,2] Output: 3 (cannot rob both index 0 and 2) Input: nums = [1,2,3,1] Output: 4
Intuition
How to Think About It
Intuition
The circular constraint means house 0 and house n-1 cannot both be robbed. DP works by breaking the circular dependency: either house 0 is robbed (exclude n-1) or it is not (exclude 0). The answer is the max of these two independent linear House Robber runs.
Core Concept
rob_range(nums, l, r) = House Robber I on nums[l..r]. Answer = max(rob_range(0, n-2), rob_range(1, n-1)). Single-element array: return nums[0].
When to use
Linear DP with a circular boundary - any "no-adjacent" selection on a ring.
When NOT to use
When the circular dependency is more complex (e.g., every k-th element is connected) - need a different cycle-breaking strategy.
Key Insights
What to Know Cold
- Two-run trick elegantly handles the circular constraint without modifying the core algorithm.
- Both sub-runs must use the same O(1) rolling-variable House Robber I implementation.
- Edge case n=1: must return nums[0] before splitting, otherwise both sub-arrays are empty.
- The two ranges [0..n-2] and [1..n-1] cover all cases: one includes the first house (excluding last), the other includes the last (excluding first).
- House Robber III (tree) uses a different approach - this trick is specific to linear/circular arrays.
1 example
Worked Examples
Circular rob [1,2,3,1]
Four houses in a circle; cannot rob adjacent including wrap-around.
Two separate rob_range calls on [0..n-2] and [1..n-1].
Output: 4
Shows how to decompose a circular constraint into two independent linear problems - a reusable technique for ring-topology DP.