Skip to main content

198. House Robber

mediumAsked at Gusto

Maximise the sum of non-adjacent elements. Gusto asks this as a clean introductory DP problem — they want you to derive the recurrence yourself and then compress the O(n) space solution to O(1) without being prompted.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2025-10)— Cited in Gusto SWE phone-screen reports as a clean DP warm-up problem with a follow-up on the circular variant.
  • Blind (2025-08)— Gusto threads mention House Robber as an entry-point DP problem used to assess recurrence derivation skills.

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. Adjacent houses have security systems connected — if two adjacent houses are broken into on the same night, the police will be alerted. Given an integer array nums representing the amount of money in 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 0 (1) and house 2 (3). Total = 4.

Example 2

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

Explanation: Rob houses 0, 2, and 4 (2 + 9 + 1 = 12).

Approaches

1. Bottom-up DP with array

dp[i] = max money robbable from first i+1 houses. dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — either skip this house or rob it (plus the best from two houses back).

Time
O(n)
Space
O(n)
function rob(nums) {
  const n = nums.length;
  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: O(n) time and space. Clear base cases. Good starting point before the space optimisation.

2. O(1) space (rolling variables)

Only dp[i-1] and dp[i-2] are needed at each step. Replace the array with two variables.

Time
O(n)
Space
O(1)
function rob(nums) {
  let prev2 = 0; // dp[i-2]
  let prev1 = 0; // dp[i-1]
  for (const amount of nums) {
    const curr = Math.max(prev1, prev2 + amount);
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

Tradeoff: O(1) space. Initialise both prev1 and prev2 to 0 (representing the empty prefix) — this elegantly handles single-element and two-element arrays without special casing.

Gusto-specific tips

Gusto interviewers want you to derive the recurrence: 'At each house I have two choices — skip it (take the best from the previous house) or rob it (take its amount plus the best from two houses back). The recurrence is dp[i] = max(dp[i-1], dp[i-2] + nums[i]).' Then evolve to O(1) space by narrating that only the last two values matter.

Common mistakes

  • Using dp[i] = max(dp[i-1], nums[i] + nums[i-2]) instead of dp[i-2] — should accumulate dp values, not raw nums.
  • Not handling the single-element array — either handle it as a base case or use the zero-initialised rolling approach which handles it naturally.
  • Initialising prev1 to nums[0] and prev2 to 0 — works but requires careful reasoning; initialising both to 0 is simpler.
  • Confusing 'non-adjacent' with 'every other' — you can skip more than one house between robberies.

Follow-up questions

An interviewer at Gusto may pivot to one of these next:

  • House Robber II (LC 213) — houses arranged in a circle; can't rob first and last simultaneously.
  • House Robber III (LC 337) — houses arranged in a binary tree; adjacent = parent/child.
  • What if you could rob at most k houses in total?

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 initialise prev1 and prev2 to 0 in the rolling approach?

They represent the maximum amount achievable from an empty prefix. This makes the first iteration (curr = max(0, 0 + nums[0]) = nums[0]) correct without special cases.

Is greedy (always take the larger of two adjacent houses) correct?

No — a locally greedy choice can block a globally better distant house. DP considers all sub-combinations correctly.

What does dp[i] represent exactly?

The maximum amount robbed from the subarray nums[0..i] — with the constraint that no two adjacent houses in that subarray are robbed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →