Skip to main content

26. House Robber

easyAsked at Snowflake

Maximize loot from non-adjacent houses. Snowflake asks this as a 1D-DP warm-up before harder DP problems; the rolling-two-variable variant is also a model for incremental aggregation state.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake new-grad onsite as DP warm-up.
  • LeetCode Discuss (2025-10)— Reported at Snowflake intern screens.

Problem

You are a professional 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 (1) and house 3 (3). Total = 4.

Example 2

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

Explanation: Rob house 1 (2), 3 (9), and 5 (1). Total = 12.

Approaches

1. Recursive with memo

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

Time
O(n)
Space
O(n)
function rob(nums) {
  const memo = new Map();
  function helper(i) {
    if (i < 0) return 0;
    if (memo.has(i)) return memo.get(i);
    const r = Math.max(helper(i - 1), helper(i - 2) + nums[i]);
    memo.set(i, r);
    return r;
  }
  return helper(nums.length - 1);
}

Tradeoff: Correct, but uses O(n) memo + recursion stack. Mention as the natural first pass.

2. Bottom-up two-variable DP (optimal)

Maintain prev (best up to i-2) and curr (best up to i-1). New best = max(curr, prev + nums[i]).

Time
O(n)
Space
O(1)
function rob(nums) {
  let prev = 0, curr = 0;
  for (const n of nums) {
    const next = Math.max(curr, prev + n);
    prev = curr;
    curr = next;
  }
  return curr;
}

Tradeoff: Single pass, O(1) state. Matches the shape of incremental aggregation.

Snowflake-specific tips

Snowflake interviewers want you to articulate the recurrence first, then collapse to two variables. Bonus signal: tie this to materialized-view incremental refresh — the recurrence depends only on bounded prior state, the same property that lets a streaming aggregate avoid full recompute.

Common mistakes

  • Confusing 'non-adjacent' with 'every other' — you can skip more than one house if profitable.
  • Initial conditions wrong — start with prev = 0, curr = 0.
  • Mutating prev before using it on the next iteration.

Follow-up questions

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

  • House Robber II (LC 213) — circular street.
  • House Robber III (LC 337) — houses arranged in a binary tree.
  • How does this relate to incremental materialized view refresh?

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 two variables instead of dp[]?

The recurrence only looks back two steps. Storing the full array wastes O(n) space when only two cells are ever needed.

How does this connect to materialized views?

An incremental MV's aggregate at time T depends only on its state at T-1 plus new rows — bounded history is what makes streaming aggregation tractable. House Robber is the same shape.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →