House Robber

MediumDynamic ProgrammingArrayDynamic Programming

Problem

Houses are lined up in a row, each holding a known amount of money, and a security system links any two adjacent houses so that robbing both in one night trips the alarm. Determine the largest total amount you can collect without ever picking two houses that sit next to each other.

Example. For houses holding [2, 7, 9, 3, 1], the best plan robs houses at positions 0, 2, and 4 for 2 + 9 + 1 = 12.

Key idea

Checking every subset of non-adjacent houses is exponential, since each house can independently be included or skipped. The fix: the best achievable total up through any house depends only on two smaller versions of the same question: the best total through the previous house, and the best total through the house before that.

Walk the houses left to right. At each house, either skip it, so the running best carries over unchanged from the previous house, or rob it, so the running best becomes its own value plus the best total from two houses back, since the immediate neighbor is now off-limits. Take whichever option is larger as the new running best. By the last house, that value is the answer, and only the two most recent running values ever needed to be remembered.

Solution

function rob(nums: number[]): number {
  let prevBest = 0; // best total through the previous house
  let prevPrevBest = 0; // best total through two houses back

  for (const money of nums) {
    const robCurrent = prevPrevBest + money;
    const best = Math.max(prevBest, robCurrent); // skip this house or rob it, take the larger
    prevPrevBest = prevBest;
    prevBest = best;
  }

  return prevBest;
}

Complexity

  • Time: O(n). A single left-to-right pass over the houses.
  • Space: O(1). Only the previous two running totals are kept.

Watch out for

  • Handle short inputs directly: zero houses means nothing to rob; one house means robbing it is always correct.
  • The "rob" option must reach back two houses, not one, or adjacent robberies would slip through.
  • This is not the same as picking the largest values overall; a big house between two other big houses may still have to be skipped.

Pattern

This is the "choose or skip under an adjacency constraint" linear DP pattern. It reappears directly in House Robber II with a circular layout, and more generally whenever a problem forbids selecting two neighboring elements.

Related questions