House Robber: maximize loot without robbing neighbors
An Apple interviewer opens with a scenario: "You're planning which houses to rob on a street. Each house has some cash, but you can't rob two adjacent houses or the alarm goes off. What's the most you can steal?" This is House Robber. It's a Blind 75 classic that shows up at Apple, Yahoo, Microsoft, Google, and Databricks. The problem is a good introduction to 1D dynamic programming.
TL;DR
At each house you make a binary choice. You rob it and add its value to the best total from two houses back, or you skip it and keep the best total from the previous house. Store these best totals in an array dp, where dp[i] is the most money from houses 0 to i. Set dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]). Then fill the rest with dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) and return the last entry. One pass, O(n) time, O(n) space.
The Problem
You are a robber planning which houses to rob along a street. The houses are in a row, and nums[i] is the amount of money in house i. Adjacent houses have connected alarms, so you can't rob two houses that are next to each other. Return the most money you can rob.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 400
rob([2,7,9,3,1]) => 12
rob([2,1,1,2]) => 4
For the first example, rob houses 0, 2, and 4 (values 2, 9, and 1) for a total of 12. For the second, rob the first and last houses for a total of 4. The best choice there skips two houses in a row, so taking every other house is not enough.
The DP Recurrence
Define dp[i] as the most money you can rob from houses 0 through i. At each house, you have two options:
- Skip house
i: Keep the best you could do up to housei - 1, which isdp[i - 1]. - Rob house
i: Takenums[i]plus the best you could do up to housei - 2. Robbing houseimeans you must skip housei - 1.
The recurrence is dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]).
Two base cases start the table. dp[0] is nums[0], because with one house you rob it. dp[1] is max(nums[0], nums[1]), because with two houses you can rob only one of them. The answer is dp[n - 1].
Walkthrough: [1,2,3,1]
Loading visualization...
Fill the table from left to right:
- House 0 (value 1):
dp[0] = 1. - House 1 (value 2):
dp[1] = max(1, 2) = 2. - House 2 (value 3):
dp[2] = max(dp[1], dp[0] + 3) = max(2, 4) = 4. Rob houses 0 and 2. - House 3 (value 1):
dp[3] = max(dp[2], dp[1] + 1) = max(4, 3) = 4. Skip it.
The answer is dp[3] = 4.
Walkthrough: [2,7,9,3,1]
Loading visualization...
The table fills to [2, 7, 11, 11, 12]. The key step is house 2 (value 9). At that point dp[1] = 7 and dp[0] = 2. The solution computes max(7, 2 + 9) = 11, so robbing houses 0 and 2 beats robbing house 1 alone. At the last house, max(11, 11 + 1) = 12.
The Rob-or-Skip Decision
Loading visualization...
Every entry comes from the same comparison. Is dp[i - 2] + nums[i] (rob this house and add the best total that does not touch its neighbor) larger than dp[i - 1] (skip this house)? The max() call makes this choice in one expression.
Edge Cases
Non-Adjacent Maximization
Loading visualization...
For [100,1,1,100], the best plan robs the first and last houses (indices 0 and 3) for 200. The table is [100, 100, 101, 200]. At house 3, dp[1] + 100 = 200 beats dp[2] = 101. Robbing those two houses skips two houses in a row, which a plan of taking every other house would miss.
All Zeroes
Loading visualization...
When every house has zero money, every entry of dp is 0 and the answer is 0. No special handling is needed.
Single House
With [1], return 1 directly. The code checks for one house before it builds the table, because dp[1] does not exist when there is only one house.
Implementation
Prefer a different language? Jump to solutions in other languages.
public class Solution {
/**
* Calculates the maximum amount of money that can be robbed without alerting the police.
*
* @param nums An array representing the amount of money in each house.
* @return The maximum amount of money that can be robbed.
*/
public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}
Here is how the code maps to the recurrence:
- The first
ifreturnsnums[0]when there is one house, so the code never readsnums[1]or writesdp[1]out of bounds. dphas one entry per house.dp[0]anddp[1]are the two base cases.- The
forloop starts at house 2 and appliesdp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]). dp[nums.length - 1]is the most money from all the houses, which is the answer.
Complexity Analysis
Time: O(n)
One pass through the array. Each house takes one addition and one comparison.
Space: O(n)
The dp array has one entry per house. There is no recursion.
From the DP Array to Two Variables
The recurrence for dp[i] reads only dp[i - 1] and dp[i - 2]. So once an entry is more than two steps behind, the loop never reads it again. You can replace the array with two variables that keep the last two entries and shift them forward at each step. That version gives the same answer in O(1) space. It is a good follow-up to mention in an interview, after the array version works. The array version is easier to trace and debug, which is why this post teaches it first.
Common Mistakes
-
Skipping the single-house check. The code sets
dp[1] = max(nums[0], nums[1]). With one house,nums[1]does not exist, so the checkif nums.length == 1must come first. -
Setting
dp[1] = nums[1].dp[1]is the best total from the first two houses. If house 0 has more money,dp[1]must benums[0], notnums[1]. -
Taking every other house. Summing the even indices and the odd indices and returning the larger sum fails on
[2,1,1,2]. The best plan robs houses 0 and 3, which skips two houses in a row. -
Trying to track which houses were robbed. The problem asks only for the largest sum. Recording the chosen houses adds code without changing the answer.
Interview Tips
- State the recurrence clearly. "At each house, I take the larger of skipping it, which keeps the best from one house back, or robbing it, which adds its value to the best from two houses back."
- Explain the base cases. "
dp[0]is the first house.dp[1]is the larger of the first two houses, because I can rob only one of them." - Trace through both examples. Fill the table for
[2,7,9,3,1]and[2,1,1,2], and show eachmax()as you go. - Mention the space follow-up. "Each entry reads only the two before it, so I can replace the array with two variables and get O(1) space."
- Mention House Robber II. "House Robber II adds a circular constraint. You solve it by running this algorithm twice: once without the first house and once without the last."
Related Problems
House Robber is the starting point for a family of non-adjacent selection problems:
- House Robber II: Houses arranged in a circle. Run the algorithm twice (without the first element, then without the last) and take the max.
- House Robber III: Houses arranged as a binary tree. Use DFS with two return values per node (rob this node vs. skip this node).
- Delete and Earn: Group array elements by value, compute the total for each value, then apply House Robber on the sorted value totals.
- Paint House: Minimize painting cost with the constraint that no two adjacent houses share a color. Same DP structure with multiple states per position.
The "rob or skip" choice from House Robber appears in all of these. The constraint always comes down to: "you can't select two adjacent items."
Ready to practice DP problems? Firecode sequences related problems using spaced repetition so you build intuition for DP recurrences over time. Over 50,000 engineers have used it to prepare for interviews at top companies like Apple, Google, and Amazon.
Solutions in Other Languages
Python
from typing import List
class Solution:
"""
Determines the maximum amount of money that can be robbed without alerting the police.
:param List[int] nums: List of integers representing the amount of money in each house.
:return: Maximum amount of money that can be robbed.
:rtype: int
"""
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[len(nums) - 1]
JavaScript
class Solution {
/**
* Calculates the maximum amount of money that can be robbed without alerting the police.
*
* @param {number[]} nums - The array representing the amount of money in each house.
* @returns {number} - The maximum amount of money that can be robbed.
*/
rob(nums) {
if (nums.length === 1) return nums[0];
const dp = new Array(nums.length).fill(0);
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];
}
}
module.exports = Solution;
TypeScript
class Solution {
/**
* Calculates the maximum amount of money that can be robbed without alerting the police.
*
* @param nums - An array representing the amount of money in each house.
* @returns The maximum amount of money that can be robbed.
*/
rob(nums: number[]): number {
if (nums.length === 1) return nums[0];
const dp: number[] = new Array(nums.length).fill(0);
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];
}
}
export { Solution };
C++
#include "HelperFuncs.h"
#include <vector>
#include <algorithm>
class Solution {
public:
/**
* Calculates the maximum amount of money that can be robbed without alerting the police.
*
* @param nums Vector of integers representing the amount of money in each house.
* @return The maximum amount of money that can be robbed.
*/
int rob(std::vector<int> &nums) {
if (nums.size() == 1) return nums[0];
std::vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
dp[1] = std::max(nums[0], nums[1]);
for (size_t i = 2; i < nums.size(); i++) {
dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.size() - 1];
}
};
Go
package solution
// Rob calculates the maximum amount of money that can be robbed without alerting the police.
//
// Parameters:
// - nums: A slice of integers representing the amount of money in each house.
//
// Returns:
// - The maximum amount of money that can be robbed.
func (s *Solution) Rob(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
dp := make([]int, len(nums))
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i := 2; i < len(nums); i++ {
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
}
return dp[len(nums)-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// Solution is required to run your method. Do not modify.
type Solution struct {
}
Scala
class Solution {
/**
* Calculates the maximum amount of money that can be robbed without alerting the police.
*
* @param nums Array representing the amount of money in each house.
* @return The maximum amount of money that can be robbed.
*/
def rob(nums: Array[Int]): Int = {
if (nums.length == 1) return nums(0)
val dp = new Array[Int](nums.length)
dp(0) = nums(0)
dp(1) = Math.max(nums(0), nums(1))
for (i <- 2 until nums.length) {
dp(i) = Math.max(dp(i - 1), dp(i - 2) + nums(i))
}
dp(nums.length - 1)
}
}
Kotlin
class Solution {
/**
* Calculates the maximum amount of money that can be robbed without alerting the police.
*
* @param nums An array representing the amount of money in each house.
* @return The maximum amount of money that can be robbed.
*/
fun rob(nums: IntArray): Int {
if (nums.size == 1) return nums[0]
val dp = IntArray(nums.size)
dp[0] = nums[0]
dp[1] = maxOf(nums[0], nums[1])
for (i in 2 until nums.size) {
dp[i] = maxOf(dp[i - 1], dp[i - 2] + nums[i])
}
return dp[nums.size - 1]
}
}
Swift
import Foundation
class Solution {
/**
* Calculates the maximum amount of money that can be robbed without alerting the police.
*
* - Parameter nums: An array representing the amount of money in each house.
* - Returns: The maximum amount of money that can be robbed.
*/
func rob(_ nums: [Int]) -> Int {
if nums.count == 1 {
return nums[0]
}
var dp = [Int](repeating: 0, count: nums.count)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in 2..<nums.count {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
}
return dp[nums.count - 1]
}
}
Rust
pub struct Solution;
impl Solution {
/// Calculates the maximum amount of money that can be robbed without alerting the police.
///
/// # Arguments
/// * `nums` - A vector of integers representing the amount of money in each house.
///
/// # Returns
/// The maximum amount of money that can be robbed.
pub fn rob(&self, nums: Vec<i32>) -> i32 {
if nums.len() == 1 {
return nums[0];
}
let mut dp = vec![0; nums.len()];
dp[0] = nums[0];
dp[1] = nums[0].max(nums[1]);
for i in 2..nums.len() {
dp[i] = dp[i - 1].max(dp[i - 2] + nums[i]);
}
dp[nums.len() - 1]
}
}
C#
public class Solution {
/// <summary>
/// Calculates the maximum amount of money that can be robbed without alerting the police.
/// </summary>
/// <param name="nums">An array representing the amount of money in each house.</param>
/// <returns>The maximum amount of money that can be robbed.</returns>
public int rob(int[] nums) {
if (nums.Length == 1) {
return nums[0];
}
int[] dp = new int[nums.Length];
dp[0] = nums[0];
dp[1] = Math.Max(nums[0], nums[1]);
for (int i = 2; i < nums.Length; i++) {
dp[i] = Math.Max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.Length - 1];
}
}
Dart
class Solution {
/// Calculates the maximum amount of money that can be robbed without alerting the police.
///
/// [nums] An array representing the amount of money in each house.
/// Returns the maximum amount of money that can be robbed.
int rob(List<int> nums) {
if (nums.length == 1) {
return nums[0];
}
List<int> dp = List.filled(nums.length, 0);
dp[0] = nums[0];
dp[1] = nums[0] > nums[1] ? nums[0] : nums[1];
for (int i = 2; i < nums.length; i++) {
dp[i] = dp[i - 1] > dp[i - 2] + nums[i] ? dp[i - 1] : dp[i - 2] + nums[i];
}
return dp[nums.length - 1];
}
}
PHP
<?php
class Solution {
/**
* Calculates the maximum amount of money that can be robbed without alerting the police.
*
* @param array $nums An array of integers representing the amount of money in each house.
* @return int The maximum amount of money that can be robbed.
*/
public function rob(array $nums): int {
if (count($nums) === 1) {
return $nums[0];
}
$dp = array_fill(0, count($nums), 0);
$dp[0] = $nums[0];
$dp[1] = max($nums[0], $nums[1]);
for ($i = 2; $i < count($nums); $i++) {
$dp[$i] = max($dp[$i - 1], $dp[$i - 2] + $nums[$i]);
}
return $dp[count($nums) - 1];
}
}
Ruby
class Solution
# Calculates the maximum amount of money that can be robbed without alerting the police.
#
# @param nums [Array<Integer>] Array representing the amount of money in each house.
# @return [Integer] The maximum amount of money that can be robbed.
def rob(nums)
return nums[0] if nums.length == 1
dp = Array.new(nums.length, 0)
dp[0] = nums[0]
dp[1] = [nums[0], nums[1]].max
(2...nums.length).each do |i|
dp[i] = [dp[i - 1], dp[i - 2] + nums[i]].max
end
dp[nums.length - 1]
end
end