Frontend Beauty
ESC

Type to search the knowledge base.

House Robber

Max money from houses in a line without adjacent robs — DP recurrence, O(1) space roll, and circular follow-up.

intermediate3 min read
  • dsa
  • dp
  • interview
  • Google
  • Meta

The problem

nums[i] = money in house i. Rob non-adjacent houses only. Maximize total.

[1,2,3,1] → 4  // 1 + 3
[2,7,9,3,1] → 12 // 2 + 9 + 1

Brute: recursion include/exclude

function robBrute(nums: number[]): number {
  function dfs(i: number): number {
    if (i >= nums.length) return 0;
    return Math.max(nums[i] + dfs(i + 2), dfs(i + 1));
  }
  return dfs(0);
}
Time O(2^n)
Space O(n)

Memoize → O(n).

Optimal DP

dp[i] = max money using houses 0..i
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
function rob(nums: number[]): number {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  let prev2 = 0; // dp[i-2]
  let prev1 = 0; // dp[i-1]

  for (const x of nums) {
    const cur = Math.max(prev1, prev2 + x);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}
Time O(n)
Space O(1)

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

x prev2 prev1 cur
2 0 0 2
7 0 2 7
9 2 7 11
3 7 11 11
1 11 11 12

Edge cases

  • Empty → 0
  • One house
  • Two houses → max of them
  • All zeros

Common mistakes

  • Forcing rob of house 0
  • Off-by-one on i-2
  • Confusing with circular (House Robber II)

Interview delivery

  1. Adjacent constraint.
  2. Recurrence max(skip, take).
  3. Roll two variables.
  4. Trace.
  5. O(n)/O(1).

Mental model

At house i you either skip it (take dp[i-1]) or rob it (take dp[i-2]+nums[i]). Optimal substructure is textbook 1D DP. Rolling two variables is the same recurrence with constant memory.

Draw the decision for a 4-house example once; the pattern sticks.

Complexity table

Approach Time Space
Exponential DFS O(2^n) O(n)
Memo DFS O(n) O(n)
DP array O(n) O(n)
Two vars O(n) O(1)

Out-loud answer

“Max non-adjacent sum on a line. dp = max(skip, take). Roll prev1/prev2. Empty zero, single house that value. O(n)/O(1). Circular version is House Robber II.”

Worked example [2,7,9,3,1] again as decisions

  • At 2: take 2.
  • At 7: take 7 beats 2.
  • At 9: 7 vs 2+9 → 11.
  • At 3: 11 vs 7+3 → 11.
  • At 1: 11 vs 11+1 → 12.

Say this sequence out loud while coding the loop variables.

Interview delivery

  1. Non-adjacent constraint.
  2. Recurrence.
  3. O(1) space roll.
  4. Bases.
  5. Mention circular follow-up only if asked.

Further reading