#153

House Robber

medium

arraydynamic-programming

You are planning to rob houses arranged in a single line. nums[i] is the amount of money stashed in house i.

Every house is wired to a shared security system: robbing two houses that are directly adjacent (indices i and i + 1) on the same night trips the alarm. Given nums, return the maximum total amount you can rob without robbing two adjacent houses.

Example

Input: nums = [1,2,3,1]

Output: 4

Rob houses 0 and 2: 1 + 3 = 4.

Constraints

0 <= nums.length <= 100
0 <= nums[i] <= 1000

Intuition

A first pass just tries both choices at every house — rob it (and skip straight past the next one), or leave it standing — and recurses on whatever's left, keeping whichever choice pays more.

function rob(nums) {
  // Best haul available from house i to the end of the street.
  function solve(i) {
    // Ran off the end of the street — nothing left to rob.
    if (i >= nums.length) return 0;
    // Option 1: rob this house, which trips the alarm on i + 1, so skip straight to i + 2.
    const robIt = nums[i] + solve(i + 2);
    // Option 2: leave this house alone and move to the very next one.
    const skipIt = solve(i + 1);
    return Math.max(robIt, skipIt);
  }
  return solve(0);
}

Brute force — try rob-it or skip-it at every house, no memo: O(2^n).

This is O(2^n) — every house branches the recursion in two, and the same starting index gets re-solved from multiple paths (rob house 0 then decide from house 2 onward, or skip house 0, skip house 1, and arrive at that same 'decide from house 2 onward' question a second time). Can we do better?

The key observation: solve(i) — the best haul from house i to the end — depends only on i, not on which houses were robbed before it. Once it's answered, it never changes, so it's only worth solving once. That's the overlapping-subproblems signature dynamic programming exists for.

Flip the recursion around and fill it bottom-up instead: let dp[i] be the best haul using only houses 0..i. At each house you either skip it (dp[i-1]) or rob it and add to the best haul from two houses back (dp[i-2] + nums[i]): dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Only the last two dp values are ever needed to compute the next one, so the stored solution never keeps the array at all — it rolls two variables forward instead. curr here is dp[i] and prev is dp[i-1], once house i has been folded in.

Walking it through:

houses: [5, 3, 4, 11, 2]

i↓

113

dp[0] = nums[0] = 5

Base case: with only one house available, the best haul is just robbing it.

i↓

113

dp[1] = max(dp[0], nums[1]) = max(5, 3) = 5 → skip house 1

Robbing house 1 alone only nets 3, worse than the 5 already banked from house 0 — skipping keeps the bigger run alive. (There's no dp[-1] yet, so `prev` starts at 0.)

i↓

113

dp[2] = max(dp[1], dp[0] + nums[2]) = max(5, 5 + 4) = 9 → rob house 2

Now robbing pays off: house 2's 4 stacked on dp[0]'s 5 beats just carrying dp[1]'s 5 forward.

i↓

113

dp[3] = max(dp[2], dp[1] + nums[3]) = max(9, 5 + 11) = 16 → rob house 3

House 3's 11 is large enough that robbing it plus dp[1]'s 5 beats carrying dp[2]'s 9 forward.

113

i↓

dp[4] = max(dp[3], dp[2] + nums[4]) = max(16, 9 + 2) = 16 → skip house 4

House 4 only adds 2 to dp[2]'s 9 (11 total) — worse than keeping dp[3]'s 16. Final answer: 16, from robbing houses 0 and 3.

Optimization

Rolling 1-D DP

Let dp[i] be the best haul using only houses 0..i. At each house you either skip it (dp[i-1]) or rob it and add to the best haul from two houses back (dp[i-2] + nums[i]): dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Only the last two values are ever needed, so two rolling variables replace the array.

O(n) time, O(1) space.

function rob(nums) {
  // prev = best haul two houses back, curr = best haul one house back.
  let prev = 0;
  let curr = 0;
  for (const money of nums) {
    // Either skip this house (curr) or rob it plus the best from two back (prev + money).
    const next = Math.max(curr, prev + money);
    prev = curr;
    curr = next;
  }
  return curr;
}

Complexity analysis

Time complexity: O(n). Here's why:

The loop runs once for every house in nums — n iterations total, with prev/curr seeded at 0 to stand in for the (nonexistent) houses before index 0, so no separate base-case pass is needed.
Each iteration does O(1) work: one addition, one comparison, and sliding prev/curr forward.

So the whole fill is O(n), down from the brute force's O(2ⁿ) — each house's best-haul-from-here answer is computed exactly once instead of re-derived on every rob/skip path that reaches it.

Space complexity: O(1). Here's why:

Only two rolling variables, prev and curr, are kept — never a full dp array of size n.
There's no recursion, so no call stack to add on top.

Same story as climbing stairs: dp[i] only ever reads dp[i-1] and dp[i-2], so the table collapses to O(1) instead of the O(n) a naive array-backed fill would use.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
nums = []	0	Empty street — nothing to rob.
nums = [7]	7	Single house — no adjacency constraint to worry about, rob it outright.
nums = [9,1]	9	Two houses — the constraint forces a choice between them; the larger one wins even though it comes first.
nums = [2,4,8,9,9,3]	19	Irregular values with no obvious pattern — rob houses 0, 2, and 4 for 2 + 8 + 9 = 19.
nums = [100,1,1,100]	200	Two big payouts separated by two small ones — skipping both small houses in a row to bank both big ones is optimal.
nums = [6,6,6,6,6]	18	All houses pay the same — robbing every other house (0, 2, 4) still beats any adjacent pair: 6 + 6 + 6 = 18.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor