Loading…

mediumDynamic ProgrammingLC #198Frequently asked

House Robber

Q: How do you solve House Robber using the Brute Force — Recursion Over Take/Skip approach?

When to use it: Say this first to expose the decision tree and justify the recurrence, then flag the exponential blowup before moving on. Frame the street as a sequence of binary decisions. Standing at house `i`, you either **rob it** — collect `nums[i]` and you're forced to skip to `i+2` — or **skip it** and move to `i+1` with nothing. The best you can do from `i` is the max of those two futures. **The mental shift: from 'which subset?' to 'what's my next move?'.** The brute-force instinct is to enumerate all valid subsets, but that's hard to reason about. Reframing it as a per-house take/skip turns the whole problem into one clean recurrence with two branches. Each branch encodes the adjacency rule automatically: robbing jumps by two, skipping jumps by one, so you can never select neighbors. **Why greedy ('rob every other house') is wrong.** It's the trap answer. On `[2, 1, 1, 2]` alternating gives `2 + 1 = 3`, but robbing the two ends gives `2 + 2 = 4`. The optimal choice at each house depends on the whole rest of the street, which is exactly why we need DP and not a fixed pattern. **Why we don't ship this.** `rob(i+2)` and `rob(i+1)` overlap heavily — the same suffix gets recomputed across branches, so the tree is exponential. State the cost, then cache it. Time complexity: O(2ⁿ). Space complexity: O(n).

Q: How do you solve House Robber using the Top-Down Memoization approach?

When to use it: The first fix once you spot the overlap — 'I'll cache rob(i) so each suffix is solved once'. Keep the identical take/skip recurrence, but cache `rob(i)` the first time it's computed. A `memo` array indexed by house starts 'empty'; each call checks the cache before recursing and writes the result before returning. **The mental shift: the suffix starting at i has one answer, so compute it once.** In the brute force, `rob(2)` might be reached through 'skip 0, skip 1' and again through other branches — each path recomputing the same suffix. Memoizing turns the exponential tree into n unique subproblems, each evaluated a single time. **Why top-down is the gentle first step.** You don't have to reason about iteration order — the recursion naturally resolves dependencies from the base case outward. You literally take the working recursion, add a cache check at the top and a cache write at the bottom, and the complexity collapses to linear. **Why the sentinel matters.** Money can be 0, so 0 is a *valid* answer and can't double as 'uncomputed'. Use -1 (loot is never negative) so the cache check never mistakes a real zero answer for a miss. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve House Robber using the Bottom-Up — Two Rolling Variables (Optimal) approach?

When to use it: The answer they want. Frame it as 'each house only needs the best totals from one and two houses back, so two variables replace the whole array'. Walk the street left to right keeping two running totals: `rob1` is the best loot achievable up to *two* houses ago, and `rob2` is the best up to the *previous* house. At each house with value `x`, the best you can do is either skip it (keep `rob2`) or rob it (`rob1 + x`, since robbing forbids the immediately previous house). Take the max, then slide both variables forward. **The mental shift: the only history that matters is two totals.** A full `dp[]` array works, but `dp[i]` reads only `dp[i-1]` and `dp[i-2]` — everything older is dead. So `rob1` and `rob2` *are* the DP table, compressed. `rob1 + x` is the 'rob this house' branch because `rob1` deliberately excludes the previous house; `rob2` is the 'skip this house' branch. **Why this also subsumes the base cases.** Seeding both variables to 0 means an empty street returns 0, and a single house returns `max(0, 0 + nums[0]) = nums[0]` — no special-casing required. The zeros represent 'no money before the street started'. **Why the slide order matters.** Compute `newRob` from the *current* `rob1` and `rob2` first, then advance `rob1 = rob2` and `rob2 = newRob`. Update them in the wrong order and you'd feed a just-updated value back into the same iteration, double-counting a house. This is the same line-ordering discipline as rolling Fibonacci. Time complexity: O(n). Space complexity: O(1).

LCPractice

Dynamic Programming · 4 of 44 · 9 min

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, given by the array nums.

The only constraint stopping you is that adjacent houses have connected security systems — robbing two directly adjacent houses on the same night will automatically alert the police.

Return the **maximum amount of money** you can rob tonight without alerting the police.

In plain English

Choose a subset of houses with no two adjacent, maximizing the total money. It's a max-weight independent set on a path graph — but because it's a simple line, a left-to-right DP solves it in linear time.

Examples

Example 1

Input: nums = [1, 2, 3, 1]
Output: 4
Note: Rob house 0 (1) and house 2 (3) → 4. Robbing 1 and 3 gives only 3.

Example 2

Input: nums = [2, 7, 9, 3, 1]
Output: 12
Note: Rob houses 0, 2, 4 → 2 + 9 + 1 = 12. Beats robbing 7 + 3 = 10.

Example 3

Input: nums = [2, 1, 1, 2]
Output: 4
Note: Rob houses 0 and 3 → 2 + 2 = 4. The naive 'every other house' (2 + 1 = 3) is worse — proof that greedy fails.

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 400

Clarifying questions4First question: Can I rob non-adjacent houses freely?Explore questions

Q1.Can I rob non-adjacent houses freely?
Yes — the only rule is no two directly adjacent houses. Houses i and i+2 are both fair game.
Q2.Can the money in a house be zero or negative?
Values are 0..400, so non-negative. Robbing never hurts the total, but a 0-value house still can't sit next to another robbed house.
Q3.Is the street a line or a circle?
A line here — the first and last houses are NOT adjacent. The circular version is House Robber II.
Q4.What should I return for an empty street?
0. With a single house, return its value. Seeding the rolling variables with zeros handles both without special cases.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

For each house you either skip it (keep dp[i-1]) or rob it (take nums[i] + dp[i-2]) — you can't rob two adjacent houses. The recurrence is dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Memoize the recursion, then collapse it to two rolling variables for O(n) time and O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can model a constrained optimization as a per-element take/skip decision, write the max recurrence with the correct i-2 dependency, and compress to O(1) space.

Where candidates slip

Assuming the answer is just 'rob every other house' (a greedy that fails on [2,1,1,2]), or pulling the 'take' branch from dp[i-1] instead of dp[i-2].

How to stand out

Disprove the greedy with a counterexample out loud, derive the recurrence cleanly, then optimize to two variables and note the circular/tree follow-ups build on this exact core.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion Over Take/Skip	`O(2ⁿ)`	`O(n)`	Say this first to expose the decision tree and justify the recurrence, then flag the exponential blowup before moving on.	Read
2	Top-Down Memoization	`O(n)`	`O(n)`	The first fix once you spot the overlap — 'I'll cache rob(i) so each suffix is solved once'.	Read
3	Bottom-Up — Two Rolling Variables (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'each house only needs the best totals from one and two houses back, so two variables replace the whole array'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMax loot, no two adjacent housesGreedy 'every other house'?TemptingModel as DPExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion Over Take/Skip

TimeO(2ⁿ)SpaceO(n)

Say this first to expose the decision tree and justify the recurrence, then flag the exponential blowup before moving on.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Stand at house i and ask: what are my only two choices, and what do they each forbid?

2Hint 2Explore hint

If you rob i you collect nums[i] but must jump to i+2; if you skip i you move to i+1 with nothing collected. Take the better of the two.

3Hint 3Explore hint

Write rob(i) = max(nums[i] + rob(i+2), rob(i+1)), returning 0 once i runs past the end.

A · Core idea

Frame the street as a sequence of binary decisions. Standing at house i, you either rob it — collect nums[i] and you're forced to skip to i+2 — or skip it and move to i+1 with nothing. The best you can do from i is the max of those two futures.

The mental shift: from 'which subset?' to 'what's my next move?'. The brute-force instinct is to enumerate all valid subsets, but that's hard to reason about. Reframing it as a per-house take/skip turns the whole problem into one clean recurrence with two branches. Each branch encodes the adjacency rule automatically: robbing jumps by two, skipping jumps by one, so you can never select neighbors.

Why greedy ('rob every other house') is wrong. It's the trap answer. On [2, 1, 1, 2] alternating gives 2 + 1 = 3, but robbing the two ends gives 2 + 2 = 4. The optimal choice at each house depends on the whole rest of the street, which is exactly why we need DP and not a fixed pattern.

Why we don't ship this. rob(i+2) and rob(i+1) overlap heavily — the same suffix gets recomputed across branches, so the tree is exponential. State the cost, then cache it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 2, 3, 1]

rob(3)

max(1 + rob(5), rob(4)) = max(1, 0) = 1

Staterob(3) = 1

Final result4

C · Code with teaching comments

Reference implementation previewpublic int rob(int[] nums) { return robFrom(nums, 0); } private int robFrom(int[] nums, int i) {Explore the full code

solution.javaJava

Brute Force — Recursion Over Take/Skip — reference

3 teaching notes

1
public int rob(int[] nums) {
2
    return robFrom(nums, 0);
3
}
4
 
5
private int robFrom(int[] nums, int i) {
6
    // Base case: walking past the last house yields no money — return 0.
7
    if (i >= nums.length) {
8
        return 0;
9
    }
10
    // Rob house i, then the next legal house is i+2 — the +2 jump enforces 'no
11
    // adjacent'.
12
    int robThis = nums[i] + robFrom(nums, i + 2);
13
    int skipThis = robFrom(nums, i + 1);
14
    // Best of the two choices. It's max because we maximize loot, not count paths.
15
    return Math.max(robThis, skipThis);
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

Notice that rob(i) depends only on i, yet the naive tree solves the same rob(i) many times from different paths. That overlap is the universal cue that a recursion is secretly a polynomial DP waiting for a cache.

ComplexityO(2ⁿ) time, O(n) space — Each call branches into two (rob-and-skip-two vs skip-one), forming a tree with up to ~2ⁿ nodes. Recursion depth is O(n) for the stack.

E · Edge cases and pitfalls4nums = [5] — rob(0) = max(5 + rob(2), rob(1)) = max(5, 0) = 5 — single house is always robbed.Explore edge cases

Edge cases handled

nums = [5]rob(0) = max(5 + rob(2), rob(1)) = max(5, 0) = 5 — single house is always robbed.

Pitfalls

Pulling the rob branch from i+1 instead of i+2 — lets you rob adjacent houses.
Returning a non-zero value past the end — corrupts the base case.
Reaching for a fixed 'alternate houses' greedy — provably wrong on [2,1,1,2].

03.2

Approach 2 of 3

Top-Down Memoization

TimeO(n)SpaceO(n)

The first fix once you spot the overlap — 'I'll cache rob(i) so each suffix is solved once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

rob(i) always returns the same number for a given i. How do you avoid recomputing it?

2Hint 2Explore hint

Add a memo array indexed by i. On entry, return the cached value if it exists; otherwise compute and store it.

3Hint 3Explore hint

memo[i] = max(nums[i] + solve(i+2), solve(i+1)), saved before returning.

A · Core idea

Keep the identical take/skip recurrence, but cache rob(i) the first time it's computed. A memo array indexed by house starts 'empty'; each call checks the cache before recursing and writes the result before returning.

The mental shift: the suffix starting at i has one answer, so compute it once. In the brute force, rob(2) might be reached through 'skip 0, skip 1' and again through other branches — each path recomputing the same suffix. Memoizing turns the exponential tree into n unique subproblems, each evaluated a single time.

Why top-down is the gentle first step. You don't have to reason about iteration order — the recursion naturally resolves dependencies from the base case outward. You literally take the working recursion, add a cache check at the top and a cache write at the bottom, and the complexity collapses to linear.

Why the sentinel matters. Money can be 0, so 0 is a valid answer and can't double as 'uncomputed'. Use -1 (loot is never negative) so the cache check never mistakes a real zero answer for a miss.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [2, 7, 9, 3, 1]

solve(4)

max(1 + 0, 0) = 1, store

Statememo[4] = 1

Final result12

C · Code with teaching comments

Reference implementation previewpublic int rob(int[] nums) { int[] memo = new int[nums.length]; Arrays.fill(memo, -1); return solve(nums, 0, memo); }Explore the full code

solution.javaJava

Top-Down Memoization — reference

3 teaching notes

1
public int rob(int[] nums) {
2
    int[] memo = new int[nums.length];
3
    // -1 marks 'uncomputed'. Critical because 0 is a legitimate loot value and can't
4
    // double as the sentinel.
5
    Arrays.fill(memo, -1);
6
    return solve(nums, 0, memo);
7
}
8
 
9
private int solve(int[] nums, int i, int[] memo) {
10
    if (i >= nums.length) {
11
        return 0;
12
    }
13
    // Cache hit — return instantly. This guard converts the exponential tree into n
14
    // one-time computations.
15
    if (memo[i] != -1) {
16
        return memo[i];
17
    }
18
    int robThis = nums[i] + solve(nums, i + 2, memo);
19
    int skipThis = solve(nums, i + 1, memo);
20
    // Store the best result for suffix i before returning so it's never recomputed.
21
    memo[i] = Math.max(robThis, skipThis);
22
    return memo[i];
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Memoization is the bridge every DP problem crosses: it proves your recurrence correct while making it fast, before you ever worry about tabulation or space. If you can write the recursion, you can almost always memoize it mechanically.

ComplexityO(n) time, O(n) space — There are n distinct subproblems (one per starting index). Each is computed once with O(1) work after its children are cached → O(n) time, O(n) for the memo plus recursion stack.

E · Edge cases and pitfalls5nums = [0, 0, 0] — Every branch is 0, so memo fills with zeros and returns 0 — the -1 sentinel keeps those real zeros distinct from misses.Explore edge cases

Edge cases handled

nums = [0, 0, 0]Every branch is 0, so memo fills with zeros and returns 0 — the -1 sentinel keeps those real zeros distinct from misses.
nums = [2, 1, 1, 2]Caching still lands on 4 (rob ends), proving memoization preserves the optimal, not the greedy, answer.

Pitfalls

Using 0 as the uncomputed sentinel — collides with legitimate 0 loot and causes recomputation or wrong reads.
Forgetting to store memo[i] before returning — stays exponential.
Indexing the memo by something other than i — the only state that defines a subproblem here is the starting index.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — Two Rolling Variables (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'each house only needs the best totals from one and two houses back, so two variables replace the whole array'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build the best-so-far loot from the left. To decide house i, what two running totals do you actually need?

2Hint 2Explore hint

Track rob1 = best up to two houses back, rob2 = best up to the previous house. Robbing the current house adds it to rob1.

3Hint 3Explore hint

Loop the houses: newRob = max(rob2, rob1 + x); then slide rob1 = rob2, rob2 = newRob. Answer is rob2.

A · Core idea

Walk the street left to right keeping two running totals: rob1 is the best loot achievable up to two houses ago, and rob2 is the best up to the previous house. At each house with value x, the best you can do is either skip it (keep rob2) or rob it (rob1 + x, since robbing forbids the immediately previous house). Take the max, then slide both variables forward.

The mental shift: the only history that matters is two totals. A full dp[] array works, but dp[i] reads only dp[i-1] and dp[i-2] — everything older is dead. So rob1 and rob2 are the DP table, compressed. rob1 + x is the 'rob this house' branch because rob1 deliberately excludes the previous house; rob2 is the 'skip this house' branch.

Why this also subsumes the base cases. Seeding both variables to 0 means an empty street returns 0, and a single house returns max(0, 0 + nums[0]) = nums[0] — no special-casing required. The zeros represent 'no money before the street started'.

Why the slide order matters. Compute newRob from the current rob1 and rob2 first, then advance rob1 = rob2 and rob2 = newRob. Update them in the wrong order and you'd feed a just-updated value back into the same iteration, double-counting a house. This is the same line-ordering discipline as rolling Fibonacci.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [2, 7, 9, 3, 1]

Array state

x=2

best = max(0, 0+2) = 2

i ↓

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result12

C · Code with teaching comments

solution.javaJava

Bottom-Up — Two Rolling Variables (Optimal) — optimal

4 teaching notes

1
public int rob(int[] nums) {
2
    // rob1 = best up to i-2, rob2 = best up to i-1. Zeros mean 'no money before the
3
    // street' and handle empty/single-house inputs.
4
    int rob1 = 0, rob2 = 0;
5
    for (int x : nums) {
6
        // Skip this house (rob2) vs rob it (rob1 + x). rob1 excludes the previous
7
        // house, so adding x stays legal.
8
        int newRob = Math.max(rob2, rob1 + x);
9
        // Slide: previous best becomes the new two-back. Must run before rob2 is
10
        // overwritten.
11
        rob1 = rob2;
12
        // Advance the running best to include the current house's decision.
13
        rob2 = newRob;
14
    }
15
    return rob2;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Once a 1D DP only reaches back a constant number of cells, the array is overkill — keep exactly that many rolling variables. House Robber reaches back two, so two variables give O(1) space. The very same compression powers Climbing Stairs and is the trick interviewers love to see you reach for unprompted.

ComplexityO(n) time, O(1) space — One pass over n houses with O(1) work each → O(n) time. Only two integers are kept regardless of n → O(1) space.

E · Edge cases and pitfalls5nums = [] — Loop never runs, rob2 stays 0 → returns 0. The zero-seed handles empty input for free.Explore edge cases

Edge cases handled

nums = []Loop never runs, rob2 stays 0 → returns 0. The zero-seed handles empty input for free.
nums = [5]One iteration: newRob = max(0, 0+5) = 5 → returns 5.

Pitfalls

Updating rob2 before rob1 in Java — feeds the new value back in and double-counts the current house.
Returning rob1 instead of rob2 — off-by-one that gives the answer excluding the last house.
Special-casing length 0 and 1 unnecessarily — the zero seeds already cover both.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int rob(int[] nums) { int rob1 = 0, rob2 = 0; for (int x : nums) { int newRob = Math.max(rob2, rob1 + x); rob1 = rob2;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Greedy alternate-house selection

Robbing strictly every other house ignores that a better combination may skip two in a row. On [2,1,1,2] it picks 2+1=3 but the optimum is 2+2=4.

Explore the code comparison

Don't write this

return sum(nums[i] for i in range(0, len(nums), 2))

Write this instead

rob1, rob2 = 0, 0
for x in nums:
    rob1, rob2 = rob2, max(rob2, rob1 + x)
return rob2

Robbing from the wrong predecessor

When you rob house i you must add the best total that EXCLUDES house i-1 (that's dp[i-2]/rob1). Pulling from dp[i-1] permits robbing adjacent houses.

Explore the code comparison

Don't write this

int newRob = Math.max(rob2, rob2 + x);

Write this instead

int newRob = Math.max(rob2, rob1 + x);

Slide-order clobber

Overwriting rob2 before copying it into rob1 destroys the value the next step needs, double-counting the current house.

Explore the code comparison

Don't write this

rob2 = Math.max(rob2, rob1 + x);
rob1 = rob2;

Write this instead

int newRob = Math.max(rob2, rob1 + x);
rob1 = rob2;
rob2 = newRob;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

1D DP — take-or-skip with a 2-house gap

Code pattern to memorize

dp[i] = max(dp[i-1], nums[i] + dp[i-2])
base: rob1 = 0, rob2 = 0
for x in nums: rob1, rob2 = rob2, max(rob2, rob1 + x)

Rules to remember

1At each house make a binary choice: skip it (carry dp[i-1]) or rob it (nums[i] + dp[i-2]). Take the max.
2Robbing house i forbids house i-1, so the money before it must come from dp[i-2], not dp[i-1].
3This is max, not sum — you're maximizing loot, the opposite of Climbing Stairs' counting.
4Two rolling variables suffice: rob1 = best up to i-2, rob2 = best up to i-1. Slide them each step.
5Handle empty input (return 0) and a single house (return nums[0]) — the loop handles the rest cleanly if seeded with zeros.

Use this pattern when

Maximize a sum over a line of items where picking one forbids its neighbor
Each decision is a local take/skip with a constraint on adjacency
The optimum at i is built from the optimum a fixed number of items back
No grouping or ordering freedom — items are processed left to right

Choose another pattern when

Houses are in a circle (first and last are adjacent) → House Robber II, run it twice
Houses form a tree, not a line → House Robber III, post-order DP
You're counting arrangements, not maximizing a value → that's a sum DP like Climbing Stairs
Picking an item forbids a *range*, not just one neighbor → weighted interval scheduling

Interview takeaway

House Robber is the archetypal 'take-or-skip with a gap' DP. The instant you see 'can't pick adjacent', reach for dp[i] = max(skip, take + dp[i-2]). It generalizes directly to the circular and tree variants, and the rolling-variable compression is the same O(1)-space trick as Climbing Stairs.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical 1D Dynamic Programming — take-or-skip with an adjacency gap (max-weight independent set on a path). Recognize it whenever choosing an item forbids its neighbor. Same core as House Robber II/III and Delete and Earn.

Practice queueDirect variations and pattern siblings

Direct follow-ups

House Robber II
Houses in a circle — first and last are adjacent. Run the linear solver twice: once excluding house 0, once excluding the last, take the max.
House Robber III
Coming soon
Houses form a binary tree. Post-order DP returning (rob, skip) pairs per node.
Delete and Earn
Coming soon
Bucket values by their total, then it's literally House Robber on the value axis (taking v forbids v-1 and v+1).
Climbing Stairs
Same dp[i-1]/dp[i-2] two-back structure and O(1) rolling compression — but it sums to count, while this maxes to optimize.

Same pattern

←

Coin Change

Continue · Next problem

House Robber II

mediumDynamic ProgrammingLC #198Frequently asked

House Robber

LCPractice

Dynamic Programming · 4 of 44 · 9 min

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, given by the array nums.

The only constraint stopping you is that adjacent houses have connected security systems — robbing two directly adjacent houses on the same night will automatically alert the police.

Return the **maximum amount of money** you can rob tonight without alerting the police.

In plain English

Examples

Example 1

Input: nums = [1, 2, 3, 1]
Output: 4
Note: Rob house 0 (1) and house 2 (3) → 4. Robbing 1 and 3 gives only 3.

Example 2

Input: nums = [2, 7, 9, 3, 1]
Output: 12
Note: Rob houses 0, 2, 4 → 2 + 9 + 1 = 12. Beats robbing 7 + 3 = 10.

Example 3

Input: nums = [2, 1, 1, 2]
Output: 4
Note: Rob houses 0 and 3 → 2 + 2 = 4. The naive 'every other house' (2 + 1 = 3) is worse — proof that greedy fails.

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 400

Clarifying questions4First question: Can I rob non-adjacent houses freely?Explore questions

Q1.Can I rob non-adjacent houses freely?
Yes — the only rule is no two directly adjacent houses. Houses i and i+2 are both fair game.
Q2.Can the money in a house be zero or negative?
Values are 0..400, so non-negative. Robbing never hurts the total, but a 0-value house still can't sit next to another robbed house.
Q3.Is the street a line or a circle?
A line here — the first and last houses are NOT adjacent. The circular version is House Robber II.
Q4.What should I return for an empty street?
0. With a single house, return its value. Seeding the rolling variables with zeros handles both without special cases.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can model a constrained optimization as a per-element take/skip decision, write the max recurrence with the correct i-2 dependency, and compress to O(1) space.

Where candidates slip

Assuming the answer is just 'rob every other house' (a greedy that fails on [2,1,1,2]), or pulling the 'take' branch from dp[i-1] instead of dp[i-2].

How to stand out

Disprove the greedy with a counterexample out loud, derive the recurrence cleanly, then optimize to two variables and note the circular/tree follow-ups build on this exact core.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion Over Take/Skip	`O(2ⁿ)`	`O(n)`	Say this first to expose the decision tree and justify the recurrence, then flag the exponential blowup before moving on.	Read
2	Top-Down Memoization	`O(n)`	`O(n)`	The first fix once you spot the overlap — 'I'll cache rob(i) so each suffix is solved once'.	Read
3	Bottom-Up — Two Rolling Variables (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'each house only needs the best totals from one and two houses back, so two variables replace the whole array'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion Over Take/Skip

TimeO(2ⁿ)SpaceO(n)

Say this first to expose the decision tree and justify the recurrence, then flag the exponential blowup before moving on.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Stand at house i and ask: what are my only two choices, and what do they each forbid?

2Hint 2Explore hint

If you rob i you collect nums[i] but must jump to i+2; if you skip i you move to i+1 with nothing collected. Take the better of the two.

3Hint 3Explore hint

Write rob(i) = max(nums[i] + rob(i+2), rob(i+1)), returning 0 once i runs past the end.

A · Core idea

Why we don't ship this. rob(i+2) and rob(i+1) overlap heavily — the same suffix gets recomputed across branches, so the tree is exponential. State the cost, then cache it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 2, 3, 1]

rob(3)

max(1 + rob(5), rob(4)) = max(1, 0) = 1

Staterob(3) = 1

Final result4

C · Code with teaching comments

Reference implementation previewpublic int rob(int[] nums) { return robFrom(nums, 0); } private int robFrom(int[] nums, int i) {Explore the full code

solution.javaJava

Brute Force — Recursion Over Take/Skip — reference

3 teaching notes

1
public int rob(int[] nums) {
2
    return robFrom(nums, 0);
3
}
4
 
5
private int robFrom(int[] nums, int i) {
6
    // Base case: walking past the last house yields no money — return 0.
7
    if (i >= nums.length) {
8
        return 0;
9
    }
10
    // Rob house i, then the next legal house is i+2 — the +2 jump enforces 'no
11
    // adjacent'.
12
    int robThis = nums[i] + robFrom(nums, i + 2);
13
    int skipThis = robFrom(nums, i + 1);
14
    // Best of the two choices. It's max because we maximize loot, not count paths.
15
    return Math.max(robThis, skipThis);
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(2ⁿ) time, O(n) space — Each call branches into two (rob-and-skip-two vs skip-one), forming a tree with up to ~2ⁿ nodes. Recursion depth is O(n) for the stack.

E · Edge cases and pitfalls4nums = [5] — rob(0) = max(5 + rob(2), rob(1)) = max(5, 0) = 5 — single house is always robbed.Explore edge cases

Edge cases handled

nums = [5]rob(0) = max(5 + rob(2), rob(1)) = max(5, 0) = 5 — single house is always robbed.

Pitfalls

Pulling the rob branch from i+1 instead of i+2 — lets you rob adjacent houses.
Returning a non-zero value past the end — corrupts the base case.
Reaching for a fixed 'alternate houses' greedy — provably wrong on [2,1,1,2].

03.2

Approach 2 of 3

Top-Down Memoization

TimeO(n)SpaceO(n)

The first fix once you spot the overlap — 'I'll cache rob(i) so each suffix is solved once'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

rob(i) always returns the same number for a given i. How do you avoid recomputing it?

2Hint 2Explore hint

Add a memo array indexed by i. On entry, return the cached value if it exists; otherwise compute and store it.

3Hint 3Explore hint

memo[i] = max(nums[i] + solve(i+2), solve(i+1)), saved before returning.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [2, 7, 9, 3, 1]

solve(4)

max(1 + 0, 0) = 1, store

Statememo[4] = 1

Final result12

C · Code with teaching comments

Reference implementation previewpublic int rob(int[] nums) { int[] memo = new int[nums.length]; Arrays.fill(memo, -1); return solve(nums, 0, memo); }Explore the full code

solution.javaJava

Top-Down Memoization — reference

3 teaching notes

1
public int rob(int[] nums) {
2
    int[] memo = new int[nums.length];
3
    // -1 marks 'uncomputed'. Critical because 0 is a legitimate loot value and can't
4
    // double as the sentinel.
5
    Arrays.fill(memo, -1);
6
    return solve(nums, 0, memo);
7
}
8
 
9
private int solve(int[] nums, int i, int[] memo) {
10
    if (i >= nums.length) {
11
        return 0;
12
    }
13
    // Cache hit — return instantly. This guard converts the exponential tree into n
14
    // one-time computations.
15
    if (memo[i] != -1) {
16
        return memo[i];
17
    }
18
    int robThis = nums[i] + solve(nums, i + 2, memo);
19
    int skipThis = solve(nums, i + 1, memo);
20
    // Store the best result for suffix i before returning so it's never recomputed.
21
    memo[i] = Math.max(robThis, skipThis);
22
    return memo[i];
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5nums = [0, 0, 0] — Every branch is 0, so memo fills with zeros and returns 0 — the -1 sentinel keeps those real zeros distinct from misses.Explore edge cases

Edge cases handled

nums = [0, 0, 0]Every branch is 0, so memo fills with zeros and returns 0 — the -1 sentinel keeps those real zeros distinct from misses.
nums = [2, 1, 1, 2]Caching still lands on 4 (rob ends), proving memoization preserves the optimal, not the greedy, answer.

Pitfalls

Using 0 as the uncomputed sentinel — collides with legitimate 0 loot and causes recomputation or wrong reads.
Forgetting to store memo[i] before returning — stays exponential.
Indexing the memo by something other than i — the only state that defines a subproblem here is the starting index.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — Two Rolling Variables (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'each house only needs the best totals from one and two houses back, so two variables replace the whole array'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build the best-so-far loot from the left. To decide house i, what two running totals do you actually need?

2Hint 2Explore hint

Track rob1 = best up to two houses back, rob2 = best up to the previous house. Robbing the current house adds it to rob1.

3Hint 3Explore hint

Loop the houses: newRob = max(rob2, rob1 + x); then slide rob1 = rob2, rob2 = newRob. Answer is rob2.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [2, 7, 9, 3, 1]

Array state

x=2

best = max(0, 0+2) = 2

i ↓

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result12

C · Code with teaching comments

solution.javaJava

Bottom-Up — Two Rolling Variables (Optimal) — optimal

4 teaching notes

1
public int rob(int[] nums) {
2
    // rob1 = best up to i-2, rob2 = best up to i-1. Zeros mean 'no money before the
3
    // street' and handle empty/single-house inputs.
4
    int rob1 = 0, rob2 = 0;
5
    for (int x : nums) {
6
        // Skip this house (rob2) vs rob it (rob1 + x). rob1 excludes the previous
7
        // house, so adding x stays legal.
8
        int newRob = Math.max(rob2, rob1 + x);
9
        // Slide: previous best becomes the new two-back. Must run before rob2 is
10
        // overwritten.
11
        rob1 = rob2;
12
        // Advance the running best to include the current house's decision.
13
        rob2 = newRob;
14
    }
15
    return rob2;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — One pass over n houses with O(1) work each → O(n) time. Only two integers are kept regardless of n → O(1) space.

E · Edge cases and pitfalls5nums = [] — Loop never runs, rob2 stays 0 → returns 0. The zero-seed handles empty input for free.Explore edge cases

Edge cases handled

nums = []Loop never runs, rob2 stays 0 → returns 0. The zero-seed handles empty input for free.
nums = [5]One iteration: newRob = max(0, 0+5) = 5 → returns 5.

Pitfalls

Updating rob2 before rob1 in Java — feeds the new value back in and double-counts the current house.
Returning rob1 instead of rob2 — off-by-one that gives the answer excluding the last house.
Special-casing length 0 and 1 unnecessarily — the zero seeds already cover both.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int rob(int[] nums) { int rob1 = 0, rob2 = 0; for (int x : nums) { int newRob = Math.max(rob2, rob1 + x); rob1 = rob2;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Greedy alternate-house selection

Robbing strictly every other house ignores that a better combination may skip two in a row. On [2,1,1,2] it picks 2+1=3 but the optimum is 2+2=4.

Explore the code comparison

Don't write this

return sum(nums[i] for i in range(0, len(nums), 2))

Write this instead

rob1, rob2 = 0, 0
for x in nums:
    rob1, rob2 = rob2, max(rob2, rob1 + x)
return rob2

Robbing from the wrong predecessor

When you rob house i you must add the best total that EXCLUDES house i-1 (that's dp[i-2]/rob1). Pulling from dp[i-1] permits robbing adjacent houses.

Explore the code comparison

Don't write this

int newRob = Math.max(rob2, rob2 + x);

Write this instead

int newRob = Math.max(rob2, rob1 + x);

Slide-order clobber

Overwriting rob2 before copying it into rob1 destroys the value the next step needs, double-counting the current house.

Explore the code comparison

Don't write this

rob2 = Math.max(rob2, rob1 + x);
rob1 = rob2;

Write this instead

int newRob = Math.max(rob2, rob1 + x);
rob1 = rob2;
rob2 = newRob;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

1D DP — take-or-skip with a 2-house gap

Code pattern to memorize

dp[i] = max(dp[i-1], nums[i] + dp[i-2])
base: rob1 = 0, rob2 = 0
for x in nums: rob1, rob2 = rob2, max(rob2, rob1 + x)

Rules to remember

1At each house make a binary choice: skip it (carry dp[i-1]) or rob it (nums[i] + dp[i-2]). Take the max.
2Robbing house i forbids house i-1, so the money before it must come from dp[i-2], not dp[i-1].
3This is max, not sum — you're maximizing loot, the opposite of Climbing Stairs' counting.
4Two rolling variables suffice: rob1 = best up to i-2, rob2 = best up to i-1. Slide them each step.
5Handle empty input (return 0) and a single house (return nums[0]) — the loop handles the rest cleanly if seeded with zeros.

Use this pattern when

Maximize a sum over a line of items where picking one forbids its neighbor
Each decision is a local take/skip with a constraint on adjacency
The optimum at i is built from the optimum a fixed number of items back
No grouping or ordering freedom — items are processed left to right

Choose another pattern when

Houses are in a circle (first and last are adjacent) → House Robber II, run it twice
Houses form a tree, not a line → House Robber III, post-order DP
You're counting arrangements, not maximizing a value → that's a sum DP like Climbing Stairs
Picking an item forbids a *range*, not just one neighbor → weighted interval scheduling

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

House Robber II
Houses in a circle — first and last are adjacent. Run the linear solver twice: once excluding house 0, once excluding the last, take the max.
House Robber III
Coming soon
Houses form a binary tree. Post-order DP returning (rob, skip) pairs per node.
Delete and Earn
Coming soon
Bucket values by their total, then it's literally House Robber on the value axis (taking v forbids v-1 and v+1).
Climbing Stairs
Same dp[i-1]/dp[i-2] two-back structure and O(1) rolling compression — but it sums to count, while this maxes to optimize.

Same pattern

←

Coin Change

Continue · Next problem

House Robber II