Skip to main content

198. House Robber

mediumAsked at Apple

House Robber is Apple's clean 1D DP medium. dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — either skip this house or take it plus the best up to two back. Apple grades on whether you can derive that recurrence on the spot and reduce to O(1) space.

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

Source citations

Public interview reports confirming this problem appears in Apple loops.

  • Glassdoor (2026-Q1)— Apple SWE phone-screen reports list House Robber as a recurring 20-minute DP medium.
  • Blind (2025-12)— Apple new-grad and ICT3 reports cite House Robber as the canonical 1D DP introduction.

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 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 (money = 2), house 3 (money = 9) and house 5 (money = 1). Total = 2 + 9 + 1 = 12.

Approaches

1. DP array with recurrence (intuitive)

dp[i] = max profit robbing houses 0..i. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

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

Tradeoff: The recurrence is the entire problem: 'either I skip house i (so dp[i] = dp[i-1]) or I take it plus the best up to i-2 (so dp[i] = dp[i-2] + nums[i]).' Apple's preferred answer for clarity.

2. DP with O(1) space (optimal)

Same recurrence but only the last two values are needed.

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

Tradeoff: Same time, O(1) space. Apple loves this optimization because it shows you noticed the recurrence only needs the last two states. Lead with the array version, then immediately offer this as the optimization.

Apple-specific tips

Apple is grading whether you can state the choice at every step: 'at house i, I either skip (carrying dp[i-1] forward) or rob (taking nums[i] plus dp[i-2], because i-1 is forbidden). Take the max.' That sentence is the entire problem. The space optimization to two scalars is bonus polish that takes the score from 7 to 9.

Common mistakes

  • Initializing dp[1] = nums[1] instead of max(nums[0], nums[1]).
  • Going around the array (circular) — that's House Robber II (LC 213), a different problem.
  • Forgetting the base cases for n=1 in the array version (return nums[0]).

Follow-up questions

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

  • House Robber II (LC 213) — circular street; run twice excluding first/last.
  • House Robber III (LC 337) — tree-shaped; recursion with (skip, take) tuple per node.
  • Delete and Earn (LC 740) — same shape after grouping by value.

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 max(prev1, prev2 + n) work?

Two choices at house i: skip (max so far is prev1) or rob (current value + max from two-back, which is prev2). The max of these two is the best at i.

Why two-back and not three-back?

Because the constraint is only NO TWO ADJACENT. House i-2 is allowed alongside i. And dp[i-2] is already optimized to include whatever non-adjacent choices were best up to i-2.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →