House robber
easyRob house i and you must have skipped i−1, so you add to dp[i−2]. The adjacency constraint lives entirely in that index gap - and only two previous values are ever read.
O(n)Space O(1) after the rolling-variable optimisationSaved in this browser - no sign-up, nothing sent anywhere.
How house robber works
dp[i] is the best haul from the first i + 1 houses. Rob house i and house i - 1 is off limits, so the take option is dp[i-2] + a[i]; skip it and dp[i-1] carries forward untouched. The adjacency rule lives entirely in that index gap - no explicit constraint checking, just which cell the recurrence reads.
Why only two cells back? Robbing house i forbids exactly one neighbour, and every legal plan for the houses before i - 1 is already summarised inside dp[i-2] - that is the optimal substructure. Brute force over all subsets of non-adjacent houses grows exponentially; the table answers each prefix once, n cells at two reads each.
Greedy - always rob the richest available house - fails: on 3, 5, 4 it grabs the 5, blocking both neighbours, and finishes with 5, while skipping the middle collects 3 + 4 = 7. The table computes both options at every house, so it cannot make that mistake. And since only dp[i-1] and dp[i-2] are ever read, the whole array collapses into two rolling variables.
Step by step
- Take houses worth 1, 9, 2, 8. With only the first house available, the best haul is its value: dp[0] = 1.
- House 1: robbing it yields 9, far better than the 1 from skipping - dp[1] = 9. The two houses cannot both be taken.
- House 2: robbing adds 2 to dp[0] = 1 for a total of 3; skipping keeps 9. Skip - dp[2] stays 9.
- House 3: robbing adds 8 to dp[1] = 9 for 17; skipping keeps 9. Rob it - dp[3] = 17.
- Traceback: dp[3] differs from dp[2], so house 3 was robbed - jump two back. dp[1] differs from dp[0]: house 1 was robbed too.
- Houses 1 and 3, total 17, no two adjacent - and the run only ever consulted the previous two dp values.
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(1) after the rolling-variable optimisation |
Reference implementation
Python
def rob(a):
"""Maximum sum with no two adjacent elements."""
prev2, prev1 = 0, 0
for x in a:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1 # O(1) memory
def rob_table(a):
"""Same thing with the table visible."""
n = len(a)
if n == 0: return 0
dp = [0] * n
dp[0] = a[0]
for i in range(1, n):
dp[i] = max(dp[i - 1], (dp[i - 2] if i > 1 else 0) + a[i])
return dp[-1]JavaScript
function rob(a) {
let prev2 = 0, prev1 = 0;
for (const x of a) {
[prev2, prev1] = [prev1, Math.max(prev1, prev2 + x)];
}
return prev1;
}Worth noticing
Two choices per house, and one of them skips ahead
Rob house i and you must have skipped i−1, so the best you can add to is dp[i−2]. Skip it and you inherit dp[i−1] unchanged. The adjacency constraint is entirely encoded in that index gap.
The table collapses to two variables
Only dp[i−1] and dp[i−2] are ever read, so there is no reason to keep the whole array. That is the standard space optimisation for any DP with a fixed-width dependency window.
Greedy fails on this
Taking the largest value first can block two neighbours worth more together. Try [2, 7, 9, 3, 1]: grabbing 9 first looks best, but 2 + 9 + 1 = 12 beats 7 + 3 = 10 only because the DP checks both orderings.
Common pitfalls
- Getting the second base case wrong. dp[1] is max(a[0], a[1]) - the better single house - not simply a[1]. This module folds it into the loop with a zero standing in for dp[-1].
- Updating the two rolling variables in the wrong order, so the older value is overwritten before the new best uses it. Compute first, then shift.
- Assuming the last house is always robbed. dp[n-1] summarises all houses; the optimal set may well skip the final one.
- Reusing this recurrence when the houses form a circle. First and last become adjacent, and the straight-line answer can illegally include both.
Where it is used
- Maximum independent set on a path graph - this exact problem, stated in graph language.
- Scheduling with an adjacency ban - picking non-adjacent time slots or ad breaks for maximum total value.
- Delete and earn (LeetCode 740), which reduces directly to house robber on the per-value point totals.
- LeetCode 198 and its circular and tree-shaped sequels - the first DP problem most people meet.
Frequently asked questions
What is the time and space complexity of house robber?
Time is O(n) - each house is decided with one comparison. Space is O(1) after the rolling-variable optimisation, because the recurrence only reads dp[i-1] and dp[i-2]. The visualizer keeps the full O(n) table only so you can watch it fill and trace the answer back.
Why does the recurrence only look back two houses?
Robbing house i rules out exactly house i - 1, nothing further. Any legal plan for the houses before that is already summarised in dp[i-2], so adding a[i] to it is always safe. That containment of the past inside one number is the optimal substructure the table rests on.
Why does greedy fail on house robber?
Taking the richest house first can block two neighbours that together are worth more. On 3, 5, 4 greedy grabs the 5 and finishes with 5, while the table sees that 3 + 4 = 7 beats it. Local best and global best diverge - the defining greedy failure.
What changes when the houses form a circle?
The first and last houses become adjacent, so they cannot both be robbed. Run the straight-line algorithm twice - once on houses 0 to n-2, once on houses 1 to n-1 - and take the larger result. That two-pass reduction is LeetCode 213.