Skip to main content

198. House Robber

mediumAsked at Goldman Sachs

Maximize money robbed from a row of houses where you can't rob two adjacent ones. Goldman Sachs uses House Robber to test 'one-dimensional DP with two-state choice' — a recurring quant pattern dressed up as a brainteaser.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Goldman Sachs loops.

  • Glassdoor (2026-Q1)— Goldman Sachs SWE candidate reports list House Robber as a 'one-dimensional DP' question with explicit space-optimization follow-up.
  • LeetCode Discuss (2025-11)— House Robber sits in the top-25 of LeetCode's Goldman Sachs company tag.

Problem

You are a robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Examples

Example 1

Input
nums = [1,2,3,1]
Output
4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total = 1 + 3 = 4.

Example 2

Input
nums = [2,7,9,3,1]
Output
12

Explanation: Rob house 1 (2) + house 3 (9) + house 5 (1) = 12.

Approaches

1. Naive recursion

rob(i) = max(rob(i+1), nums[i] + rob(i+2)). Exponential without memoization.

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

Tradeoff: Cleanest way to articulate the recurrence. Times out for n > 30. Mention then memoize.

2. Bottom-up DP with array

dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Time
O(n)
Space
O(n)
function robDP(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  if (n === 1) return nums[0];
  const dp = new Array(n);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[n - 1];
}

Tradeoff: Clear and correct. Linear time at linear extra space. Show as the bridge to the space-optimized version.

3. Rolling-variable DP (optimal)

Only dp[i-1] and dp[i-2] are needed. Two scalars suffice.

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

Tradeoff: Constant extra space. This is what Goldman wants — same algorithm, zero memory overhead, idiomatic in any language.

Goldman Sachs-specific tips

Goldman Sachs interviewers love this question because the choice 'rob i or skip i' is a textbook two-state DP. The interviewer wants you to write the recurrence on the whiteboard before coding: max(rob[i-1], rob[i-2] + nums[i]). Show all three approach tiers (recursion → DP array → rolling vars) to demonstrate you can space-optimize from instinct.

Common mistakes

  • Greedy 'always rob the bigger of every adjacent pair' — wrong on [2,1,1,2] (greedy gives 3, optimal is 4).
  • Forgetting the n = 1 and n = 0 base cases.
  • Mixing up the indices when transitioning from 'index i' notation to 'rolling variable' notation.

Follow-up questions

An interviewer at Goldman Sachs may pivot to one of these next:

  • Houses in a circle — first and last are now adjacent. (House Robber II, LC #213.)
  • Houses in a binary tree. (House Robber III, LC #337.)
  • What if you could rob k houses non-adjacent? (Add a state for 'houses robbed so far'.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why isn't greedy correct?

Because the choice at house i affects what's available at house i+1 in a way that can flip the optimum. On [2,1,1,2], greedy picks 2 (house 1), then must skip house 2, picks 1 (house 3), must skip house 4 — total 3. Optimal robs 2 + 2 = 4 by skipping the two 1s.

Is the rolling-variable version a separate algorithm or just an optimization?

Same algorithm, smaller representation. The DP state is fully determined by the last two values, so storing them in scalars instead of an array doesn't change the computation — just the memory footprint.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill House Robber and other Goldman Sachs interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →