House Robber — Think-Aloud Framework

A repeatable way to break down an interview problem, drawn out step by step

The Decision at Each House

dp[i] = max(dp[i-1],  dp[i-2] + nums[i])
skip this house  vs  rob it + best up to 2 houses back
dp table — best total up to each house (fills as you step)
Press Step ▶ to walk the street one house at a time.

The Framework: U·M·P·I·R·E

  1. Understand — restate the problem in your own words, ask clarifying questions, lock down inputs/outputs and edge cases. "So I'm given an array of non-negative ints, and I can't pick two adjacent ones — I want the max sum of a non-adjacent subset. Can the array be empty? Can values be 0?"
  2. Match — what category is this? What pattern have I seen that fits? "'Max/min with a constraint and overlapping choices' smells like dynamic programming. Each house is a rob-or-skip decision that depends on earlier ones."
  3. Plan — design the approach OUT LOUD before coding. Define the state, recurrence, base cases. "Let dp[i] = max money using houses 0..i. At house i: skip → dp[i-1], or rob → nums[i] + dp[i-2]. Take the max. Base: dp[0]=nums[0], dp[1]=max(nums[0],nums[1])."
  4. Implement — code the plan cleanly, narrating as you go. Keep it readable. "I'll track just two variables instead of a full array since I only ever look back two steps."
  5. Review — trace your code by hand on the example you drew. "Let me walk [2,7,9,3,1] through my variables and check I get 12."
  6. Evaluate — state time/space complexity and possible trade-offs. "O(n) time, O(1) space with the rolling-variable version. The array version is O(n) space but easier to debug."

What Your Whiteboard Should Look Like

This is the actual layout to aim for during the Plan stage — example up top, dp table, then state / recurrence / base boxed off, with edge cases & complexity in the corners.

House Robber — max non-adjacent sum
in: nums[] (non-neg ints)  ·  out: one int  ·  rule: can't pick i and i+1
① EXAMPLE (draw this first!)
02
17
29
33
41
2
7
11
11
12
↑ circled picks 2 + 9 + 1 = 12  ·  ↑ red row = dp[i] filling left → right
② STATE

dp[i] = max money robbing houses 0…i

③ RECURRENCE

at house i, two choices:

  • skip → dp[i-1]
  • rob → dp[i-2] + nums[i]

dp[i] = max(skip, rob)

④ BASE CASES
  • dp[0] = nums[0]
  • dp[1] = max(nums[0], nums[1])
⑤ EDGE CASES
  • [] → 0
  • [5] → 5
  • [2,1,1,2] → 4  (ends, not middle!)
⑥ COMPLEXITY
  • time: O(n)
  • space: O(n) array → O(1) w/ 2 vars
Q for interviewer:
circular street? (HR II)
negatives allowed?

Notice the spatial layout: example top, derived facts boxed in the middle, questions & complexity in the margins. Numbering (①②③) keeps you — and the interviewer — oriented as you talk. Draw the example before the approach; the pattern often reveals itself once it's on the board.

The Final Code (narrate this as you write)

var rob = function(nums) {
  // Edge cases first — interviewers love this
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  // prev2 = best up to i-2, prev1 = best up to i-1
  let prev2 = 0;
  let prev1 = 0;

  for (let i = 0; i < nums.length; i++) {
    // rob this house + prev2,  OR  skip and keep prev1
    const curr = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;   // shift the window forward
    prev1 = curr;
  }
  return prev1;
};

Why two variables? The recurrence only ever looks back two steps, so you don't need the whole dp array — just the last two values. That drops space from O(n) to O(1). Mention the array version first, then offer this as the optimization in the Evaluate step.