Skip to main content

26. House Robber

mediumAsked at Ola

Maximize loot from a line of houses where you cannot rob two adjacent ones.

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 certain amount of money stashed; the only constraint is that adjacent houses have connected security systems. Determine 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

Example 2

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

Approaches

1. Recursive try all

Try robbing or skipping each house with naive recursion.

Time
O(2^n)
Space
O(n)
const go = i => i >= nums.length ? 0 : Math.max(nums[i] + go(i+2), go(i+1));
return go(0);

Tradeoff:

2. DP rolling two state

Keep prev and curr; at each step the new best is max(prev + nums[i], curr).

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

Tradeoff:

Ola-specific tips

Ola uses this to verify your DP fluency; relate it to picking non-overlapping surge windows to maximize revenue without burning the model.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →