· By John Kavanagh

House Robber in TypeScript: Keep the Choice, Lose the History

Rows of terraced houses beside a long straight residential street.
Image by Habib Ilmi, licensed from Unsplash.

The awkward part of House Robber isn't adding up the money. It's remembering that a good choice now can rule out a better choice next door. Picking the largest remaining value feels sensible until the neighbours arrive with an objection.

I like this problem because the final implementation is tiny, but that size is earned. Once we've described exactly what information the next decision needs, most of the apparent complexity disappears. Starting with two unexplained variables gets the same code onto the page, but leaves the useful part out.

In LeetCode's House Robber problem, we're given non‑negative amounts along a straight street and must find the largest total without selecting adjacent houses. The answer is a value, not the list of houses. That distinction will let us discard history later.


A Tempting Choice That Doesn't Survive Its Neighbours

Consider the amounts 4, 5, 4. Choosing the largest amount first gives us 5, because both neighbours become unavailable. Choosing the two outer houses gives us 8. A locally attractive choice has lost to a pair it prevented us from considering.

Another tempting shortcut is to compare the total at even positions with the total at odd positions. That handles some examples, but valid solutions can switch parity after leaving a larger gap. With 4, 1, 1, 4, the best answer is 8, from the first and last houses. Either fixed parity gives only 5.

Both mistakes discard choices without a justification. A greedy algorithm needs a reason that taking its preferred option can never spoil an optimum. Neither the largest value nor a fixed parity supplies that reason here.

A direct search would make a take‑or‑skip decision at each house, rejecting paths that select neighbours. It works, but many branches ask the same question about the remaining street. Instead of remembering every route through those branches, we can remember the best answer for each prefix.


Give the State a Precise Meaning

Let best(k) mean the largest amount available from the first k houses. This is a prefix length, so best(0) is the empty prefix and equals zero. It doesn't mean the amount obtained by definitely taking house k.

For the next house there are two exhaustive possibilities. If we skip it, the answer remains the best total from the previous prefix. If we take it, we add its value to the best prefix ending before its immediate neighbour.

The recurrence is therefore best(k) = max(best(k - 1), best(k - 2) + nums[k - 1]) for prefixes containing at least two houses. The first house has answer nums[0], because values are non‑negative. The rolling implementation below handles that first step using two initial zeroes, without indexing an imaginary negative house.

The proof follows the final choice. Every valid selection either contains the newest house or doesn't. The two branches cover those cases, and each branch uses an optimal solution to its remaining smaller problem. Taking their maximum cannot miss a better valid selection.

This is the part I would explain before discussing storage. Once that sentence is solid, reducing an array to two variables becomes bookkeeping, rather than a small act of faith.


Walk the Totals Before Compressing Them

For 3, 6, 4, 8, 2, the prefix answers are:

Houses consideredSkip newestTake newestBest total
None000
3033
3, 6366
3, 6, 4677
3, 6, 4, 871414
3, 6, 4, 8, 214914

The fourth step combines 8 with the answer for the first two houses, which is 6. It doesn't combine 8 with the immediately preceding prefix answer of 7, because that answer may include the adjacent 4.

Notice that the best total never falls as the prefix grows. Skipping the newest house always preserves the previous answer. That gives us a useful testing property, although it isn't sufficient to prove an implementation correct on its own.

We only read the previous two totals when building the next one. A complete prefix table would be perfectly reasonable for teaching or debugging, but it stores values that this particular return value never needs again.


The Complete TypeScript Solution

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

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

  return oneBack;
};

Before each iteration, oneBack contains the best total for all houses already visited. twoBack contains the best total for the prefix before the most recently visited house. We calculate the new answer before advancing either variable.

That update order matters. Assigning twoBack = oneBack before calculating best loses the older value and can allow adjacent houses into the same total. The temporary variable isn't decorative verbosity. It preserves the two different prefixes whilst we calculate their successor.

There is one pass through the input, so the running time is O(n). The additional storage is O(1). We don't mutate the input, sort it, or allocate a second array. Sorting would destroy the adjacency information that defines the problem.

Under the stated bounds, there are at most 100 houses and each value is at most 400. Even the sum of every amount is comfortably within JavaScript's exact integer range, so ordinary number arithmetic is suitable.


Tests That Challenge the Decision

I would start with a single house, all zeroes, two equal houses, and a sequence whose best answer skips the final house. Those check initialisation, ties, adjacency, and the temptation to return a total that must include the last item.

Then I'd keep both counterexamples above. 4, 5, 4 rejects largest‑first selection; 4, 1, 1, 4 rejects fixed parity. A regression example should explain which plausible mistake it catches. Otherwise a growing test list can become an impressive collection of numbers with no particular job.

For small arrays, an independent reference can enumerate every subset, reject subsets containing adjacent indices, and take the largest remaining sum. That reference is slow, but structurally different from the rolling recurrence. Comparing every short array over a small value alphabet exercises many combinations of ties and gaps without making the verifier depend on the same reasoning as the implementation.

Reversing the input should preserve the answer, since it preserves neighbour relationships. Appending a zero should also preserve it. These are useful additional properties; neither replaces checking an exact expected result.


When Two Numbers Stop Being Enough

If the caller needs the selected houses, retain a prefix table and walk backwards through the take‑or‑skip decisions. Ties may produce several equally good answers, so decide whether any optimum is acceptable before trying to make reconstruction deterministic.

A circular street changes the relationship between the first and last houses. This implementation deliberately doesn't solve that variation. Trees and wider exclusion distances also need states that reflect their own relationships. A short implementation is only useful when its assumptions travel with it.

My Climbing Stairs walkthrough also compresses a recurrence to two previous values, but there we're adding counts rather than choosing a maximum. My Coin Change article explores another state meaning again: the fewest coins needed for a total. Similar‑looking arrays do not imply interchangeable recurrences.


Wrapping Up

House Robber becomes manageable when the state describes the best answer for a prefix, rather than the last house we happened to choose. Taking or skipping the newest house gives us a complete argument, and that argument tells us exactly which two earlier answers to retain.

I'd rather remember that decision than memorise the two assignments. The assignments are easy to recover once the prefix meaning is clear, and rather less forgiving when it isn't.


Need a senior engineer involved?

I can work directly in the codebase, review the architecture, or support the team through delivery when the work needs more than extra hands.