MediumDynamic ProgrammingArrayUpdated Sep 2026

198. House Robber

Asked at Google, Microsoft, Apple, Databricks and 1 more

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Dynamic Programming

Companies

5

Problem

You are given an array nums. Each element is the amount of money inside one house on a street. The houses are in a row, and their alarms are linked: if you rob two houses that sit next to each other, the police come.

Return the largest total amount you can steal in one night without ever robbing two adjacent houses. You may skip as many houses as you like, and you do not have to rob the first or the last house.

The key rule is: no two chosen houses may be neighbors. So if you take house i, you must skip house i-1 and house i+1.

Pick houses with no neighbors

nums12310123Green houses are robbed, red houses are skippedbecause they touch a green one.
In [1,2,3,1] the best legal pick is house 0 and house 2, giving 1 + 3 = 4.

Constraints

  • ●1 <= nums.length <= 100
  • ●0 <= nums[i] <= 400

Examples

Example 1
Inputnums = [1,2,3,1]
Output4
WhyTake house 0 (money 1) and house 2 (money 3). They are not neighbors, so the alarm stays quiet. Total = 1 + 3 = 4. Taking 2 + 3 is not allowed because those houses touch.
Example 2
Inputnums = [2,7,9,3,1]
Output12
WhyTake houses 0, 2 and 4 with money 2, 9 and 1. No two of them are next to each other, and the total is 2 + 9 + 1 = 12, which is the best possible.

Asked At

5 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
DatabricksMediumView all Databricks questions →
WalmartMediumView all Walmart questions →

How to Think About It

1

At each house, you have two choices: rob this house (add its value to the best result from 2 houses back) or skip it (carry forward the best result from the previous house).

2

The recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). dp[i] is the max money you can rob from houses 0 to i.

3

Why dp[i-2] + nums[i]? If you rob house i, you can't rob house i-1. So you add nums[i] to the best you could do ending at i-2.

4

Space optimization: you only need the last two dp values. Use two variables instead of an array. This brings space from O(n) to O(1).

5

Edge cases: single house (return its value), two houses (return the larger), empty array (return 0).

Optimal Approach

Step 1: Define dp[i] = max money robbed from houses 0 to i.
Step 2: Base cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).
Step 3: For i from 2 to n-1:
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Either skip house i (keep dp[i-1]) or rob it (add nums[i] to dp[i-2]).
Step 4: Return dp[n-1].

Space optimization: use two variables prev1 (dp[i-1]) and prev2 (dp[i-2]).
For each num: new_prev1 = max(prev1, prev2 + num), prev2 = prev1.

Time: O(n). Space: O(1) optimized.

Two rolling totals

nums2793101234iStart: prev2 = 0, prev1 = 0, then take house 0 → prev1= 2nums2793101234iHouse 1: max(prev1, prev2 + 7) = max(2, 0 + 7) = 7, soprev1 becomes 7nums2793101234Finish: the rolling totals end at 12, which is houses0, 2 and 4new = max(prev1, prev2 + num)prev2 = prev1prev1 = new
At each house we keep the best total so far (prev1) and the best total from two houses back (prev2).
ComplexityTime O(n)Space O(1)We scan the array once, and we only keep the two previous best totals instead of a full dp array.

What Trips People Up in Real Interviews

1

Confusing this with "pick every other house." The constraint is no two adjacent houses, not every other house. You might skip houses non-uniformly.

2

Using recursion without memoization. That's O(2^n) and will time out. Use bottom-up DP or memoization to get O(n).

3

Forgetting that you can skip houses. At each house, you can either rob it (add to previous skip) or skip it (carry forward previous max).

4

Not handling edge cases: single house (rob it), two houses (rob the larger one).

5

Using a full dp array when only two variables are needed. Each position depends on the previous two values — use two variables for O(1) space instead of an O(n) array.

Solution Code

O(n) time
def rob(nums):
    if not nums:
        return 0
    prev1, prev2 = 0, 0
    for num in nums:
        prev1, prev2 = max(prev1, prev2 + num), prev1
    return prev1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the House Robber problem?

You are a robber planning to rob houses along a street. Each house has a certain amount of money, but adjacent houses have connected security systems. Find the maximum amount you can rob without triggering the alarm. This is a classic dynamic programming problem.

How do you solve House Robber?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask House Robber?

House Robber is asked at Google, Microsoft, Apple, Databricks, Walmart. It is a medium difficulty problem.

What are common mistakes on House Robber?
  • Confusing this with "pick every other house." The constraint is no two adjacent houses, not every other house. You might skip houses non-uniformly.
  • Using recursion without memoization. That's `O(2^n)` and will time out. Use bottom-up DP or memoization to get `O(n)`.
  • Forgetting that you can skip houses. At each house, you can either rob it (add to previous skip) or skip it (carry forward previous max).
  • Not handling edge cases: single house (rob it), two houses (rob the larger one).
  • Using a full dp array when only two variables are needed. Each position depends on the previous two values — use two variables for `O(1)` space instead of an `O(n)` array.