LeetCode · #213
House Robber II Solution
Houses are arranged in a circle. Return the maximum amount you can rob without robbing two adjacent houses (first and last are also adjacent).
01
Section One · Problem
Problem Statement
Same as House Robber (LC 198), but houses form a circle: the first house is adjacent to the last. You cannot rob both nums[0] and nums[n-1].
Example
Input: nums = [2,3,2]
Output: 3 // Can't rob house 0 and house 2 (adjacent in circle). Best: rob house 1 = 3.
Constraints
• 1 ≤ nums.length ≤ 100 • 0 ≤ nums[i] ≤ 1000
02
Section Two · Approach 1
Brute Force — O(2ⁿ)
Try all valid subsets (no two adjacent, including the wrap-around). For each subset, compute the sum and track the maximum. This is exponential in the number of houses.
Why it works
Exhaustively checking all combinations guarantees the optimal is found. The circular constraint is handled by explicitly checking that the first and last house aren't both selected.
Why we can do better
Key insight: The circular constraint means either house 0 is NOT robbed, or house n-1 is NOT robbed (or both). This lets us split the problem into two linear House Robber runs: one on
nums[0..n-2] (exclude last), one on nums[1..n-1] (exclude first). The answer is the max of both.
Java — Brute force (two linear passes, simpler)
class Solution {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
return Math.max(robLine(nums, 0, nums.length-2),
robLine(nums, 1, nums.length-1));
}
private int robLine(int[] nums, int lo, int hi) {
int prev2 = 0, prev1 = 0;
for (int i = lo; i <= hi; i++) {
int cur = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1; prev1 = cur;
}
return prev1;
}
}
Python — Two linear passes
class Solution:
def rob(self, nums: list[int]) -> int:
if len(nums) == 1: return nums[0]
def rob_line(arr):
p2 = p1 = 0 for x in arr:
p2, p1 = p1, max(p1, p2 + x)
return p1
return max(rob_line(nums[:-1]), rob_line(nums[1:]))
| Metric | Value |
|---|---|
| Time | O(n) — two linear passes |
| Space | O(1) |
03
Section Three · Approach 2
Two-Pass Linear DP — O(n) time, O(1) space
Break the circle by observing: in any optimal solution, either the first house is excluded or the last house is excluded (or both). Run the standard House Robber algorithm twice — once on nums[0..n-2], once on nums[1..n-1] — and return the maximum.
💡 Mental model: Imagine guests sitting at a round dinner table. You want to pass a dessert plate but can't serve two adjacent guests. The problem: the first and last guests sit next to each other. Solution: imagine cutting the circular table into a line at one seat. You cut it two ways — once removing the host's seat from the left end, once from the right. Solve the straight-line seating problem each way and pick whichever serves more guests. The cut guarantees you never serve both endpoints of the original circle.
Algorithm
- Base case: if
n == 1, returnnums[0](only one house, rob it). - Pass 1: run House Robber on
nums[0..n-2](might include first, definitely excludes last). - Pass 2: run House Robber on
nums[1..n-1](might include last, definitely excludes first). - Return
max(pass1, pass2).
🎯 When to recognize this pattern:
- Any "circular array with adjacent constraint" reduces to two linear subproblems.
- The signal is: "array is circular AND you can't pick adjacent elements." This reduction also applies to LC 188/309 variants with circular constraints.
Why this covers all cases:
- If the optimal solution includes house 0, it can't include house n-1 — so it's captured by pass 1.
- If it includes house n-1, it can't include house 0 — captured by pass 2.
- If it includes neither, it's captured by both passes. Therefore max(pass1, pass2) is always correct.
04
Section Four · Trace
Visual Walkthrough
Trace for nums = [1, 2, 3, 1] (circular). Expected output: 4.
House Robber II — Two Passes (nums=[1,2,3,1])
05
Section Five · Implementation
Code — Java & Python
Java — Two-pass House Robber
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(robLine(nums, 0, n-2),
robLine(nums, 1, n-1));
}
private int robLine(int[] nums, int lo, int hi) {
int prev2 = 0, prev1 = 0;
for (int i = lo; i <= hi; i++) {
int cur = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
}
Python — Two-pass House Robber
class Solution:
def rob(self, nums: list[int]) -> int:
if len(nums) == 1: return nums[0]
def rob_line(arr):
p2 = p1 = 0 for x in arr:
p2, p1 = p1, max(p1, p2 + x)
return p1
return max(rob_line(nums[:-1]), rob_line(nums[1:]))
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| Brute force recursion | O(2ⁿ) | O(n) | Exponential — handles circular check but TLE |
| DP array (two passes) | O(n) | O(n) | Two dp arrays; correct but extra space |
| Two-variable two-pass ← optimal | O(n) | O(1) | Two O(n) passes, constant space each |
Prerequisite: This problem requires having solved LC 198 (House Robber) first. The entire solution is just "run LC 198 twice on different subarrays." Understanding the linear version's DP recurrence is essential before attempting the circular version.
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| Single house | [5] | No circular issue. Must handle as special case — robLine(0,-1) would return 0. |
| Two houses | [1,2] | Adjacent in circle. Max of each alone: max(1,2)=2. |
| Three houses | [2,3,2] | Can only rob one. max(pass1=[2,3]→3, pass2=[3,2]→3)=3. |
| All equal | [5,5,5,5] | Both passes give 10. Answer=10. |
| Huge last house | [1,1,1,100] | Pass 2 captures the 100. pass1=[1,1,1]→2, pass2=[1,1,100]→101. Answer=101. |
⚠ Common Mistake: Forgetting the
n == 1 special case. With only one house, nums[0..n-2] = nums[0..-1] is empty, and nums[1..n-1] = nums[1..0] is also empty — both passes return 0. But the correct answer is nums[0]. Always guard if (n == 1) return nums[0] before the two-pass logic.