House Robber: maximize loot without robbing neighbors

AS
Ackshaey Singh
Difficulty Hard
Time Complexity
O(n)
Space Complexity
O(n)
Array Dynamic programming
Apple Yahoo Microsoft Google Cisco Databricks Amazon Arcesium Meta TikTok Bloomberg ByteDance Walmart Labs Citadel LinkedIn

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 <= 100
  • 0 <= 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:

  1. Skip house i: Keep the best you could do up to house i - 1, which is dp[i - 1].
  2. Rob house i: Take nums[i] plus the best you could do up to house i - 2. Robbing house i means you must skip house i - 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 if returns nums[0] when there is one house, so the code never reads nums[1] or writes dp[1] out of bounds.
  • dp has one entry per house. dp[0] and dp[1] are the two base cases.
  • The for loop starts at house 2 and applies dp[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 check if nums.length == 1 must 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 be nums[0], not nums[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 each max() 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

Frequently Asked Questions

What is the time complexity of the House Robber solution?
O(n). The loop fills each entry of the dp array once, and each entry takes one max() of two values. There are no nested loops and no recursion.
What is the space complexity of the House Robber solution?
O(n). The solution allocates a dp array with one entry per house. dp[i] stores the most money you can rob from houses 0 to i.
Why can't you rob adjacent houses?
Adjacent houses have connected alarms. Robbing two houses next to each other sets off the alarm. So you must skip at least one house between any two you rob, and that rule is what makes this a DP problem.
What is the recurrence relation for House Robber?
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]). At house i you either skip it and keep dp[i - 1], or rob it and add nums[i] to dp[i - 2], since robbing it means skipping house i - 1. The answer is dp[n - 1].
Can the dp array be replaced with two variables?
Yes. dp[i] reads only dp[i - 1] and dp[i - 2], so two variables that keep the last two entries give the same answer in O(1) space. The reference solution keeps the full array because it makes each step easy to trace.
What if all house values are zero?
The solution returns 0. dp[0] and dp[1] are 0, and every later max() compares two zeros, so every entry of the dp array is 0.
Does House Robber work with a single house?
Yes. With one house, the solution returns nums[0] before it builds the dp array. This check matters because the code sets dp[1], which does not exist when there is only one house.
What is House Robber II?
House Robber II arranges houses in a circle, so the first and last houses are adjacent. The solution runs House Robber twice, once without the first house and once without the last house, and returns the larger result.
Can House Robber be solved with recursion?
Yes, but plain recursion is O(2^n) because it recomputes the same subproblems. Memoization brings it to O(n) time and O(n) space. The bottom-up dp array gives the same O(n) time and O(n) space without recursion.
What are common follow-up problems to House Robber?
House Robber II (circular arrangement), House Robber III (binary tree structure where you can't rob directly connected nodes), Delete and Earn (group elements by value, then apply House Robber logic), and Paint House (minimize cost with adjacency constraints).