House Robber II
Problem
nums[i] is the cash in house
i. Robbing two neighbouring houses triggers the alarm, and the first and
last houses are neighbours too. Return the maximum amount you can take without setting off
the alarm.[2,3,2]Output3[1,2,3,1]Output4[1,2,3]Output31 ≤ n ≤ 100 · 0 ≤ nums[i] ≤ 1000
Try it yourself
class Solution {
public int rob(int[] nums) {
}
}
0 and house
n-1. So solve the ordinary line problem twice — on
[0..n-2] and on [1..n-1] — and take the larger.Instinct The best answer at position i depends only on a few earlier positions (i-1, i-2, ...) - write dp[i] from its predecessors, then roll it into variables.
Memory hack Look back, pick best, roll forward - every step only remembers the last couple of stairs it stood on.
Open the 1-D Dynamic Programming guide →Approaches
Brute ForceTwo Lines, Plain Recursion
O(2n)Space O(n)For a line [i..end]: either rob house i and jump to
i+2, or skip it and go to i+1. Run this on both
circle-breaking ranges. The two branches overlap heavily, so work grows
exponentially.
public int rob(int[] nums) { int n = nums.length; if (n == 1) return nums[0]; return Math.max(best(nums, 0, n - 2), best(nums, 1, n - 1)); } private int best(int[] nums, int i, int end) { if (i > end) return 0; return Math.max(nums[i] + best(nums, i + 2, end), best(nums, i + 1, end)); }
Shows the recurrence clearly, but explodes beyond ~40 houses.
BetterTwo Lines, Memoization
O(n)Space O(n)The answer for a range only depends on the start index i, so
cache it in memo[i] (-1 = unknown, since 0 is a valid
answer). Use a fresh memo for each of the two ranges.
public int rob(int[] nums) { int n = nums.length; if (n == 1) return nums[0]; return Math.max(best(nums, 0, n - 2, newMemo(n)), best(nums, 1, n - 1, newMemo(n))); } private int[] newMemo(int n) { int[] m = new int[n]; Arrays.fill(m, -1); return m; } private int best(int[] nums, int i, int end, int[] memo) { if (i > end) return 0; if (memo[i] != -1) return memo[i]; return memo[i] = Math.max(nums[i] + best(nums, i + 2, end, memo), best(nums, i + 1, end, memo)); }
Linear time; O(n) memo + recursion stack.
OptimalTwo Lines, Rolling Variables
O(n)Space O(1)Go left to right with dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Only the last two values matter, so keep prev2/prev1.
Run once per range and return the max.
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; // best up to i-2, best up to i-1 for (int i = lo; i <= hi; i++) { int cur = Math.max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = cur; } return prev1; }
Dry run[2,7,9,3,1] — cells show dp (best so far)
- A i=127···xA: range [0..3]
- A i=22711··xmax(7, 2+9) = 11
- A i=3271111·xmax(11, 7+3) = 11
- B i=3·x7910·B: max(9, 7+3) = 10
- B i=4·x791010ans max(11,10)=11 ✔
Two linear passes, constant memory — optimal.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Two Lines, Plain Recursion | O(2n) | O(n) |
| Better | Two Lines, Memoization | O(n) | O(n) |
| Optimal | Two Lines, Rolling Variables | O(n) | O(1) |
- Forgetting
n == 1— both ranges become empty and you return 0. - Using 0 as the memo sentinel — zero-cash ranges get recomputed forever.
- Sizing the memo by range length but indexing by absolute
i→ out of bounds.
- Solve House Robber I first, then reduce the circle to two lines.
- Explain why two cases suffice: house 0 and n-1 can never both be taken.
- Reuse one
robLine(lo, hi)helper — no array copies needed.