House Robber

1. Problem & Core Objective

Each house holds some money. You cannot rob two adjacent houses. Return the maximum you can rob.

nums = [1,2,3,1]      →  4      rob houses 0 and 2
nums = [2,7,9,3,1]    →  12     rob houses 0, 2 and 4

Constraints: 1 <= nums.length <= 100 · 0 <= nums[i] <= 400

What's actually being tested: the take-or-skip recurrence — the first question here where the recurrence involves a genuine decision rather than just combining neighbours. It's the template for a whole family: House Robber II, Best Time to Buy and Sell Stock with Cooldown, and every knapsack variant.

2. First-Principles Thought Process

The decision at each house

Standing at house i, there are exactly two options:

• Rob it — take nums[i], and you must have skipped i−1, so add the best from i−2
• Skip it — take whatever was best up to i−1

dp[i] = max(nums[i] + dp[i−2],  dp[i−1])
         └── rob ──┘             └ skip ┘

That's the take-or-skip shape, and it's the most reusable recurrence in this section.

Why greedy fails

"Always rob the biggest remaining house" is wrong. On [2,7,9,3,1] greedy takes 9, which forbids 7 and 3, leaving 2 and 1 — total 12. That happens to be right.

But on [2,1,1,2] greedy takes a 2, forbidding its neighbour, then the other 2 — total 4, which is also right.

The real failure is subtler: [5,1,1,5] — greedy takes a 5, then can't take its neighbour, then takes the other 5 = 10, correct again. Try [4,1,1,4,1]: greedy picks a 4, blocks 1, picks the other 4, blocks its neighbours → 8. DP also gives 8.

Greedy is hard to break on small inputs, which is exactly why it's dangerous — it needs a case where a locally smaller choice enables two larger ones later. The DP never needs such a case because it considers both branches at every house.

Why dp[i−2] and not dp[i−1] when robbing

Robbing i forbids i−1. The best total excluding i−1 is dp[i−2] — because dp[i−2] already represents the optimum over houses 0..i−2, none of which are adjacent to i.

It's not "skip exactly one house"; it's "the best achievable while leaving i−1 free".

Base cases

dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

The second is the one to get right: with two houses you take the larger, not the first.

3. Solution Paths

Approach 1 — Try every valid subset (brute force)

public int rob(int[] nums) {
    return robFrom(nums, 0);
}

private int robFrom(int[] nums, int i) {
    if (i >= nums.length) return 0;
    return Math.max(nums[i] + robFrom(nums, i + 2),     // rob i, skip i+1
                    robFrom(nums, i + 1));               // skip i
}

• Time O(2^n) · Space O(n) stack

Counter-questions on this approach

⭐ "Why exponential?"

Two branches at every house, so 2^n paths — and robFrom(i) is reached from both robFrom(i−1) and robFrom(i−2), recomputing the entire suffix each time.

At n = 100 that's 1.3 × 10^30 calls. Only n distinct subproblems exist, which is the DP signal.

⭐ "Why i + 2 in the rob branch?"

Because robbing house i forbids i+1, so the next decision is at i+2. Using i+1 there would allow adjacent robberies and overcount.

"Is this at least correct?"

Yes — it enumerates every valid subset and takes the maximum. That's why it's worth writing first: it's obviously correct, and memoising it is mechanical.

Approach 2 — Tabulation

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];

    int[] dp = new int[n];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);

    for (int i = 2; i < n; i++)
        dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);

    return dp[n - 1];
}

Trace — nums = [2,7,9,3,1]:

Answer 12 ✓

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "Why is dp[1] = max(nums[0], nums[1]) rather than nums[1]?"

Because dp[i] means "the best achievable considering houses 0..i", not "the best ending at i". With two houses available you take the larger — you're not obliged to rob house 1.

Setting dp[1] = nums[1] would lose the case where house 0 is bigger. On [5,1] it would return 1 instead of 5.

That definition — best over a prefix, not best ending here — is what makes the dp[i-1] skip branch meaningful.

⭐ "Why does robbing i add dp[i-2] rather than dp[i-2] restricted somehow?"

Because dp[i−2] is already the optimum over houses 0..i−2, and none of those is adjacent to i. So whatever selection achieved dp[i−2] remains valid alongside i.

The non-adjacency constraint only ever involves consecutive indices, so skipping one is sufficient — there's no longer-range interference to worry about.

"Why the n == 1 special case?"

Because dp[1] would index out of bounds on a single-element array. It's the only special case needed; n = 2 is handled by the base cases with the loop not running.

Approach 3 — Rolling variables (optimal)

public int rob(int[] nums) {
    int twoBack = 0, oneBack = 0;                  // best excluding / including the previous

    for (int num : nums) {
        int current = Math.max(num + twoBack, oneBack);
        twoBack = oneBack;
        oneBack = current;
    }
    return oneBack;
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "This has no special case for n == 1. Why not?"

Because both variables start at 0, which correctly represents "no houses considered yet, nothing robbed". The first iteration computes max(nums[0] + 0, 0) = nums[0], which is right.

Seeding from zero rather than from the array's first elements removes the base-case handling entirely — a real simplification over the tabulated version, and worth noticing.

⭐ "What do the two variables mean?"

After processing house i, oneBack is dp[i] — the best over houses 0..i — and twoBack is dp[i−1].

So when the next house is considered, twoBack is the best excluding its immediate neighbour, which is exactly what robbing requires.

Naming them by position rather than by robbed/not-robbed avoids a common confusion: oneBack is not "the best if we robbed the last house", it's "the best over everything up to the last house".

"Why does the update order matter?"

twoBack = oneBack must run after current is computed. Otherwise current would read the wrong generation and the recurrence collapses.

"Could the total overflow?"

100 houses at 400 each caps the total at 40,000 — far inside int. But note you can't rob all of them; the real maximum is about half that.

Comparison

4. Why the Optimal Wins

The recursion explores 2^n subsets when only n distinct suffixes exist. The DP considers each house once, evaluating both branches in O(1).

The rolling version additionally removes the base-case handling, because seeding both variables at 0 makes the first iteration produce nums[0] naturally.

The framing worth keeping:

Take-or-skip: dp[i] = max(take it + dp[i−2], skip it = dp[i−1]). And define dp[i] as "the best over the prefix 0..i", not "the best ending at i" — that's what makes the skip branch mean anything.

5. Java Prerequisites

The take-or-skip recurrence

dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);

Rolling with zero seeds — removes the base cases:

int twoBack = 0, oneBack = 0;
for (int num : nums) {
    int current = Math.max(num + twoBack, oneBack);
    twoBack = oneBack; oneBack = current;
}

State definition matters — dp[i] is the best over the prefix, not the best ending at i. The two differ, and only the first makes dp[i-1] a valid skip branch.

6. Interview Communication Guide

Clarifying questions: Only adjacent houses are forbidden (yes — not "every other house")? Can values be 0 (yes)? Is the array circular (no — that's House Robber II)? Must I rob at least one house (no, but all values are non-negative so it never helps to rob none)?

The pitch

"At each house there are exactly two choices. Rob it — take its value, and since that forbids the previous house, add the best from two back. Or skip it — carry forward the best up to the previous house.

So dp[i] = max(nums[i] + dp[i−2], dp[i−1]).

The definition matters: dp[i] is the best achievable over houses 0 through i, not the best ending at i. That's what makes the skip branch meaningful — and it's why dp[1] is max(nums[0], nums[1]) rather than nums[1]. On [5,1] getting that wrong returns 1 instead of 5.

And robbing i adds dp[i−2] because dp[i−2] is already the optimum over everything up to two back, none of which is adjacent to i. The constraint only ever involves consecutive indices, so skipping one is enough.

I'd avoid greedy — 'always take the largest remaining' has no way to see that a smaller choice now can enable two larger ones later. The DP evaluates both branches at every house, so it never needs to.

The recursion is O(2^n); memoising or tabulating makes it O(n). And since the recurrence reads a fixed two-cell window, two rolling variables give O(1) space.

Nice detail: seeding both variables at 0 removes the base cases entirely. The first iteration computes max(nums[0] + 0, 0) = nums[0], so there's no n == 1 guard to write."

Edge cases to volunteer:

Name [5,1]. It's the smallest case that distinguishes "best over the prefix" from "best ending here", and a solution with dp[1] = nums[1] fails it while passing most others.

7. Follow-Up Questions — Modified Constraints

⭐ "What if the houses were arranged in a circle?"

Question 4. The first and last become adjacent, so run the linear solution twice — once excluding the last house, once excluding the first — and take the larger. Two O(n) passes, which turns a circular constraint into two linear ones.

⭐ "Return which houses were robbed."

Track the decision at each index and walk back from the end. O(n) extra space — and it forfeits the O(1) rolling, since you need the full history. Same trade as in question 2.

"What if you couldn't rob houses within distance k?"

dp[i] = max(nums[i] + dp[i−k−1], dp[i−1]). Still a fixed window, so it rolls with a circular buffer of size k+1.

"What if the houses formed a tree?"

LeetCode 337, House Robber III. Same take-or-skip logic, but the recursion returns a pair — best if this node is robbed, best if not — because a parent needs both. That's the tree analogue of the two rolling variables.

"What if values could be negative?"

Then robbing nothing might be optimal, so the answer is max(dp[n−1], 0) — or the recurrence needs a max(..., 0) clamp. With non-negative values that can't happen, which is why the current version needs no clamp.

"What if n were 10^6?"

The rolling version is O(n) time and O(1) space, so it scales directly. Values at 400 each would cap the total around 2 × 10^8 — still int, but close enough to check.