Skip to main content

198. House Robber

medium

Maximize the money you can rob from a row of houses with the constraint that adjacent houses can't both be robbed. The 'rob it or skip it' decision is the cleanest DP-on-arrays starter.

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 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 amount = 1 + 3 = 4.

Example 2

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

Explanation: Rob house 1 (2) + house 3 (9) + house 5 (1) = 12.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

At each house, the choice is: rob it (add to result from i-2) or skip it (carry result from i-1).

Hint 2

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

Hint 3

Two rolling variables are enough — no DP array needed.

Solution approach

Reveal approach

Two-variable rolling DP. Maintain prev2 (best total up to house i-2) and prev1 (best total up to house i-1). For each house i, the new best is curr = max(prev1, prev2 + nums[i]) — either skip this house (prev1) or rob it (prev2 + nums[i]). Update prev2 = prev1, prev1 = curr. Initialize prev2 = 0, prev1 = 0 and loop from 0 to n-1. Return prev1. O(n) time, O(1) extra space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill House Robber and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →