Skip to main content

26. House Robber

easyAsked at Salesforce

Given an array of non-negative integers representing house values, find the max sum without robbing two adjacent houses. Salesforce uses this as the canonical 'introductory DP' problem to see if you can derive the recurrence.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses this as the gateway problem for DP-style scheduling questions.
  • Blind (2025-11)— Recurring on Salesforce L4/L5 phone 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 (money = 1) and house 3 (money = 3). Total = 4.

Example 2

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

Explanation: Rob houses 1, 3, 5 -> 2 + 9 + 1 = 12.

Approaches

1. Recursive with memoization

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

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

Tradeoff: Clear DP statement but O(n) extra space for memo + recursion stack.

2. Iterative with rolling variables

Track prev (best up to i-2) and curr (best up to i-1). Update: next = 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: O(1) space. The recurrence collapses to two rolling variables.

Salesforce-specific tips

Salesforce grades this on whether you can articulate the recurrence (skip i, or take i + skip i+1) BEFORE coding. Bonus signal: explain that this is the foundation of their scheduling problems — 'choose tasks such that no two consecutive ones overlap' uses the same DP shape.

Common mistakes

  • Defining rob(i) as 'rob from i to end' AND 'must include i' — the looser definition makes the recurrence cleaner.
  • Initializing prev or curr to nums[0] or nums[1] — easier to start both at 0 and let the loop absorb every element uniformly.
  • Computing next AFTER updating prev — clobbers the value you need.

Follow-up questions

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

  • House Robber II (LC 213) — circular street (first and last are adjacent).
  • House Robber III (LC 337) — houses in a tree.
  • Maximum Subarray (LC 53) — a relative.

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 does the rolling-variable version work?

The recurrence at position i depends only on positions i-1 and i-2, so we only need to keep those two values. Trading O(n) for O(1) without losing the DP.

Why update prev = curr BEFORE curr = next?

Because after the iteration, prev should be the prior curr (which represents 'best up to i-1' relative to the next iteration's i).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →