198. House Robber

RUN IT Can't rob adjacent — look back two steps

TYPESCRIPT The solution, annotated

function rob(nums: number[]): number {
  let rob2 = 0; // best loot up to two houses back (dp[i-2])
  let rob1 = 0; // best loot up to one house back  (dp[i-1])

  for (const n of nums) {
    const best = Math.max(rob1, rob2 + n); // skip vs rob
    rob2 = rob1;
    rob1 = best;
  }

  return rob1;
}

Reading it block by block

INTERVIEWFollow-ups they'll ask

• "What if the houses are in a circle?" House Robber II — first and last are adjacent, so run the linear solution twice: once on nums[0..n-2] and once on nums[1..n-1], and take the max.
• "Can you return which houses you robbed, not just the amount?" Keep the full dp[] array and backtrack: if dp[i] === dp[i-1] you skipped house i, otherwise you robbed it (jump to i-2).
• "What's the brute force?" Recursion with memoization (top-down DP) — try rob vs skip at each index, cache by index. Same O(n) time as bottom-up but O(n) call-stack space. The rolling version is the optimal form.
• "What if there are negative values?" The algorithm still works correctly — Math.max will simply skip any house with a negative value since not robbing it (rob1) will always be better.
• "What if k adjacent houses are off limits instead of just 1?" The recurrence becomes dp[i] = max(dp[i-1], dp[i-k-1] + nums[i]), and you'd need to keep a window of k+1 previous values instead of just two.

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

function rob(nums: number[]): number {
  let rob2 = 0; // dp[i-2]
  let rob1 = 0; // dp[i-1]

  for (const n of nums) {
    const best = Math.max(rob1, rob2 + n);
    rob2 = rob1;
    rob1 = best;
  }

  return rob1;
}

FLASHCARDS Tap to flip