Topic: Learning notes

LeetCode 198: House Robber with take-or-skip rolling states

My House Robber solution, why its p1 and p2 updates work, and a clearer O(n)-time, O(1)-extra-space rolling-state version.

House Robber continues the one-dimensional dynamic programming pattern from Climbing Stairs, but the states are no longer simply added together. At each house, I need to choose the better result between skipping it and taking it.

I received one conceptual hint after getting stuck: split the decision into take and skip, then consider the best results from one and two houses back. I wrote the implementation, complexity analysis, and assertions afterward. The solution passed, but I still need another problem to confirm that I can define the states again without a hint.

The problem

LeetCode 198: House Robber gives an array of non-negative amounts stored in houses along a street. Adjacent houses cannot both be robbed on the same night. The task is to return the maximum available amount under that restriction.

For [2, 7, 9, 3, 1], the answer is 12 by taking 2, 9, and 1. The constraints are 1 <= nums.length <= 100 and 0 <= nums[i] <= 400.

Direct search

The direct approach branches at every house: skip the current house, or take it and continue two positions later.

function robBruteForce(nums: number[], index = 0): number {
    if (index >= nums.length) return 0;

    const skip = robBruteForce(nums, index + 1);
    const take = nums[index] + robBruteForce(nums, index + 2);

    return Math.max(skip, take);
}

This code follows the problem statement, but separate branches repeatedly solve the same suffix. Its runtime has an O(2ⁿ) upper bound, and the recursion stack uses O(n) space. That growth is not practical for an input of up to 100 houses.

My solution

I kept three variables for earlier results:

function rob(nums: number[]): number {
    if (nums.length === 1) return nums[0];
    if (nums.length === 2) return Math.max(nums[0], nums[1]);

    let p1 = nums[0];
    let p2 = nums[1];
    let max = Math.max(p1, p2);

    for (let i = 2; i < nums.length; i++) {
        const curr = Math.max(nums[i] + p1, p2);
        p1 = Math.max(p1, p2);
        p2 = curr;
        max = Math.max(curr, max);
    }

    return max;
}

This implementation is correct under the problem’s constraints. During the first iteration at i = 2, p1 is the first amount and p2 is the second amount. curr compares taking the first and third houses with taking only the second. Since amounts cannot be negative, the first plus the third cannot be worse than taking only the first, so no valid best case is lost.

After that first iteration, p1 = Math.max(p1, p2) begins to hold the best result through the preceding position, while p2 holds the current best result. Later iterations therefore follow the usual dynamic programming relationship.

The output is right, but the state is awkward to describe. p2 starts as the second house’s raw amount and becomes the best prefix result only after one iteration. max separately stores a value that the rolling state already contains. The explanation also relies on the non-negative input constraint.

A clearer rolling-state version

I later reduced the same idea to two variables whose meanings never change. It needs no array-length branches and no separate max.

function rob(nums: number[]): number {
    let twoBack = 0;
    let oneBack = 0;

    for (const amount of nums) {
        const current = Math.max(oneBack, twoBack + amount);
        twoBack = oneBack;
        oneBack = current;
    }

    return oneBack;
}

Before processing the current house:

• oneBack is the best total after processing the preceding house.
• twoBack is the best total after processing the house before that.

Skipping the current house preserves oneBack. Taking it excludes the adjacent preceding house, so that candidate is twoBack + amount. Their maximum becomes current, and the states shift forward by one position.

Tracing [2, 7, 9, 3, 1]

At amount 3, taking it produces 7 + 3 = 10, while skipping it preserves 11. At the final amount 1, taking it after the best result from two positions back produces 12.

Correctness invariant

At the start of each iteration, oneBack is the maximum over every valid selection through the preceding house, and twoBack is the maximum through the house before it.

Every optimal selection belongs to exactly one of two cases. If it excludes the current house, its value cannot exceed oneBack. If it includes the current house, it must exclude the adjacent house, so its value is twoBack + amount. These cases are disjoint and exhaustive, making their maximum the correct result for the current prefix.

After the update, twoBack receives the old oneBack, and oneBack receives current. The invariant is ready for the next iteration. Once the loop finishes, oneBack is the answer for the full array.

Complexity

Both linear implementations visit each house once, so runtime is O(n). They allocate no data structure that grows with the input, giving O(1) extra space.

Executable checks

I originally supplied four assertions. I added the second official example, an all-zero case, and an input that makes state-update mistakes easier to spot:

import assert from "node:assert/strict";

assert.equal(rob([2, 1, 1, 2]), 4);
assert.equal(rob([1, 3, 3, 1]), 4);
assert.equal(rob([0]), 0);
assert.equal(rob([1, 2, 3, 1]), 4);
assert.equal(rob([2, 7, 9, 3, 1]), 12);
assert.equal(rob([5, 1, 1, 5]), 10);
assert.equal(rob([0, 0, 0, 0]), 0);

All seven cases were executed successfully. Tests check initialization and update order, but the state definition and invariant still carry the correctness argument.

Common mistakes

• Splitting the answer into even and odd indices. An optimal selection need not use only one parity.
• Adding the current amount to the best result from the adjacent house.
• Updating one rolling variable before current has used both old values.
• Keeping a maximum without defining which prefix it covers.
• Finding the recursive relation but leaving its overlapping work in place.

What I learned

Variable names in dynamic programming are part of the reasoning. If I cannot state what each value means at the start of an iteration, proving the update becomes difficult too.

My original code works within the official constraints, but explaining why p2 changes meaning after the first iteration takes extra effort. Fixing the states as the best results through one and two positions back makes the code shorter and maps each candidate directly to the problem. My next review should reproduce that invariant without looking at the formula.

References

• LeetCode 198: House Robber: official statement, examples, and constraints.
• Node.js assert: standard module used for the executable checks.