DP — House Robber II
↗ LeetCode: House Robber II · Medium · pattern chapter →
Houses in a circle — first and last adjacent. Max rob without adjacent.
Example 1 — nums=[2,3,2] → 3 (rob only house 1: 3; can't rob 0 and 2 together — adjacent in circle) Example 2 — nums=[1,2,3,1] → 4 (rob houses 0 and 2: 1+3=4) Example 3 — nums=[1] → 1
Constraints — 1 ≤ n ≤ 100. Brute 2ⁿ subset enumeration at n=100 = 2¹⁰⁰ ≈ 10³⁰ ops — at 10⁹ ops/sec that's ~10¹³ year, ~1000× universe-age. Two linear-DP runs (skip first or last) is O(n) = 200 ops = trivial.
Interview timer00:00
Approach 1 — Brute enumeration
Intuition. For each subset, check if it's a valid pick (no adjacent in circle) and track max sum. 2ⁿ states.
Complexity — Time O(2ⁿ · n); Space O(n). Dies past n=25. In an interview say "linear DP twice: once excluding last house, once excluding first → O(n)."
Approach 2 — Two linear runs (canonical)
Insight. rob(first) forbids rob(last). So the optimum = max of two independent subproblems on subarrays: [0..n-2] (skip last) and [1..n-1] (skip first). Each is standard linear House Robber.
int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(linear(nums, 0, n - 2), linear(nums, 1, n - 1));
}
int linear(int[] nums, int lo, int hi) {
int prev = 0, curr = 0;
for (int i = lo; i <= hi; i++) {
int t = Math.max(curr, prev + nums[i]);
prev = curr; curr = t;
}
return curr;
}Complexity — Time O(n); Space O(1). Say aloud in an interview: "reduce a cyclic problem to two acyclic subproblems — same technique in Circular Array Loop, Rotate Array."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute subsets | O(2ⁿ · n) | O(n) | TLE past n=25 |
| Two linear runs | O(n) | O(1) | Canonical |
When to use which
- Circular house robber → this.
- Linear → House Robber.
- Tree → House Robber III.