Skip to main content

26. House Robber

easyAsked at Vercel

Given an array of house values, find the max amount you can rob without robbing two adjacent houses. Vercel asks this as the introductory DP — the same recurrence shape as their 'pick-at-most-N-non-conflicting-deploys' scheduling logic.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-12)— Vercel screen DP warm-up.
  • Blind (2026-Q1)— Listed in Vercel platform onsite recap.

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 (money = 1) and house 3 (money = 3).

Example 2

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

Explanation: Rob houses 1, 3, 5 (2 + 9 + 1).

Approaches

1. Recursive top-down

rob(i) = max(rob(i+1), nums[i] + rob(i+2)). Memoize to avoid recomputation.

Time
O(n)
Space
O(n) memo + O(n) stack
function rob(nums) {
  const memo = new Array(nums.length).fill(-1);
  function go(i) {
    if (i >= nums.length) return 0;
    if (memo[i] !== -1) return memo[i];
    return memo[i] = Math.max(go(i + 1), nums[i] + go(i + 2));
  }
  return go(0);
}

Tradeoff: Works but uses recursion stack. The iterative DP is simpler.

2. Bottom-up DP with two variables (optimal)

Track prev and prev2. At each house, current = max(prev, prev2 + nums[i]). Slide forward.

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

Tradeoff: O(1) extra space. The two-variable rolling pattern is the canonical optimization for any DP where only the last two states matter.

Vercel-specific tips

Vercel grades the rolling two-variable optimization. Bonus signal: writing the full DP recurrence first and then explaining that you only ever need prev and prev2, so the dp[] array collapses to two scalars. This is the same shape they ask about in their fibonacci variations.

Common mistakes

  • Returning Math.max(prev, prev2) at the end — prev already holds the answer; this just adds confusion.
  • Confusing 'pick' with 'skip' — pick is prev2 + n (we skipped the previous house), skip is prev (we keep our last total).
  • Starting prev = nums[0], prev2 = 0 with a one-off — works but the cleaner version starts both at 0 and loops from index 0.

Follow-up questions

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

  • House Robber II (LC 213) — circular street.
  • House Robber III (LC 337) — binary tree of houses.
  • Delete and Earn (LC 740) — same DP shape with grouping.

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 do I only need two variables?

The recurrence only references dp[i-1] and dp[i-2]. The rest of the dp array is dead weight after each step, so collapsing to scalars saves O(n) memory.

Why not greedy (always rob max-valued)?

Greedy fails on [2, 1, 1, 2] — robbing the two 2s (positions 0 and 3) gives 4, but greedy might grab a 1 and miss the optimum.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →