Skip to main content

22. House Robber

mediumAsked at Chime

Given non-negative house values, compute the maximum amount you can rob without picking two adjacent houses.

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

Problem

You are a professional robber planning to rob houses along a street. Each house has a non-negative amount of money. You cannot rob two adjacent houses, since adjacent houses have connected security. Given an array nums representing the amount of money at each house, return the maximum amount 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

Example 2

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

Approaches

1. Exhaustive recursion

At each index, recurse on take-and-skip vs skip. Exponential without memoization.

Time
O(2^n)
Space
O(n)
function rob(i) {
  if (i >= nums.length) return 0;
  return Math.max(nums[i] + rob(i+2), rob(i+1));
}

Tradeoff:

2. Rolling DP

Track only the last two best totals: prev2 and prev1. At each house compute curr = max(prev1, prev2 + nums[i]) and shift. Constant space.

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

Tradeoff:

Chime-specific tips

Chime maps house-robber onto picking non-conflicting ACH retry slots, so emphasize how the adjacency constraint mirrors a backoff window in their retry scheduler.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →