Street Safe Heist Strategy: 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 maximum you can steal?" This is Street Safe Heist Strategy, also known as House Robber on other platforms. It's a Blind 75 classic that shows up at Apple, Yahoo, Microsoft, Google, and Databricks. The problem is a perfect introduction to 1D dynamic programming with space optimization.

TL;DR

At each house, you face a binary choice: rob it (adding its value to the best total from two houses back) or skip it (keeping the best total from the previous house). Track two variables: prev1 (best total including or excluding the previous house) and prev2 (best total from two houses back). At each step: prev1 = max(prev2 + nums[i], prev1). One pass, O(n) time, O(1) space.

The Problem

Given an array nums where each element represents the money in a house, find the maximum sum you can collect without robbing two adjacent houses.

rob([1,2,3,1]) => 4
rob([2,7,9,3,1]) => 12

For the first example, rob houses 0 and 2 (values 1 and 3) for a total of 4. For the second, rob houses 0, 2, and 4 (values 2, 9, and 1) for a total of 12.

The DP Recurrence

Define dp[i] as the maximum money you can collect from houses 0 through i. At each house, you have two options:

1. Rob house i: Take nums[i] plus the best you could do up to house i-2 (skipping i-1).
2. Skip house i: Keep the best you could do up to house i-1.

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

Since dp[i] only depends on the two previous values, you don't need an array. Two variables are enough.

Walkthrough: [1,2,3,1]

Start with prev1 = 0 and prev2 = 0. Process each house:

• House 0 (value 1): max(0 + 1, 0) = 1. Rob it.
• House 1 (value 2): max(0 + 2, 1) = 2. Rob it (better than house 0 alone).
• House 2 (value 3): max(1 + 3, 2) = 4. Rob houses 0 and 2.
• House 3 (value 1): max(2 + 1, 4) = 4. Skip it.

The answer is 4.

Walkthrough: [2,7,9,3,1]

The most interesting moment is at house 2 (value 9). At that point, prev1 = 7 (from house 1) and prev2 = 2 (from house 0). The algorithm picks max(2 + 9, 7) = 11, choosing to rob houses 0 and 2 rather than house 1 alone.

The Rob-or-Skip Decision

At every house, the algorithm makes the same calculation: is prev2 + current_value (robbing this house and combining with the best non-adjacent total) better than prev1 (skipping this house entirely)? The max() call captures this binary decision in a single expression.

Edge Cases

Non-Adjacent Maximization

For [100,1,1,100], the optimal strategy is to rob the first and last houses (indices 0 and 3) for 200. The two small houses in between are decoys. The algorithm correctly identifies this because at house 3, prev2 + 100 (100 + 100 = 200) beats prev1 (101).

All Zeroes

When every house has zero money, every max() comparison produces 0 and the answer is 0. No special handling needed.

Single House

With [1], return 1 directly. The base case handles this before the loop.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {

  public int rob(int[] nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }
    if (nums.length == 1) {
      return nums[0];
    }

    int prev1 = 0, prev2 = 0;

    for (int num : nums) {
      int temp = prev1;
      prev1 = Math.max(prev2 + num, prev1);
      prev2 = temp;
    }

    return prev1;
  }
}

The variable naming takes a moment to parse:

• prev1 tracks the maximum money collectible up to the previous house (equivalent to dp[i-1]).
• prev2 tracks the maximum money collectible up to two houses back (equivalent to dp[i-2]).
• temp saves prev1 before it gets overwritten, so prev2 can be updated correctly.

The for loop processes every house, and the max() call makes the rob-or-skip decision. After the loop, prev1 holds the answer.

Complexity Analysis

Time: O(n)

One pass through the array. Each house requires one comparison and two assignments.

Space: O(1)

Three integer variables (prev1, prev2, temp). No arrays or recursion needed.

From Full DP to Space-Optimized

The full DP approach would allocate an array of size n:

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
dp[i] = max(dp[i-2] + nums[i], dp[i-1])  for i >= 2

But since each value depends only on the two before it, the array is wasteful. Replacing it with two variables gives identical results in O(1) space. This "rolling variable" pattern applies to many 1D DP problems where the recurrence only looks back a fixed number of steps.

Common Mistakes

• Initializing prev1 and prev2 to nums[0] and nums[1]. This complicates the logic and requires separate handling for arrays of length 1 or 2. Initializing both to 0 and iterating from the start is cleaner.

• Forgetting the temp variable. If you update prev1 and then set prev2 = prev1, prev2 gets the new value, not the old one. The temp save is essential.

• Returning max(prev1, prev2) instead of just prev1. After the loop, prev1 is always >= prev2 because prev1 = max(prev2 + num, prev1) ensures prev1 never decreases. Returning just prev1 is correct.

• Trying to track which houses were robbed. The problem only asks for the maximum sum, not the actual houses. Adding index tracking makes the code more complicated without adding value.

Interview Tips

• State the recurrence clearly. "At each house, I choose the maximum of robbing it (adding to the best from two houses back) or skipping it (keeping the best from one house back)."
• Explain the space optimization. "Since each state only depends on the two previous states, I can replace the DP array with two variables. This reduces space from O(n) to O(1)."
• Trace through both examples. Walk through [1,2,3,1] and [2,7,9,3,1], showing how the variables shift at each step.
• Mention the follow-ups. "House Robber II adds a circular constraint. You solve it by running this algorithm twice: once excluding the first house and once excluding 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 (excluding first element, then excluding 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" pattern from House Robber carries into all of these. The constraint always boils 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 space-optimized 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:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        prev1, prev2 = 0, 0
        for num in nums:
            temp = prev1
            prev1 = max(prev2 + num, prev1)
            prev2 = temp

        return prev1

JavaScript

class Solution {
  rob(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];

    let prev1 = 0;
    let prev2 = 0;

    for (let num of nums) {
      let temp = prev1;
      prev1 = Math.max(prev2 + num, prev1);
      prev2 = temp;
    }

    return prev1;
  }
}

TypeScript

class Solution {
  rob(nums: number[]): number {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];

    let prev1 = 0;
    let prev2 = 0;

    for (const num of nums) {
      const temp = prev1;
      prev1 = Math.max(prev2 + num, prev1);
      prev2 = temp;
    }

    return prev1;
  }
}

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  int rob(std::vector<int> &nums) {
    if (nums.empty()) return 0;
    if (nums.size() == 1) return nums[0];

    int prev1 = 0, prev2 = 0;
    for (int num : nums) {
      int temp = prev1;
      prev1 = std::max(prev2 + num, prev1);
      prev2 = temp;
    }
    return prev1;
  }
};

Go

func (s *Solution) Rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }

    prev1, prev2 := 0, 0
    for _, num := range nums {
        temp := prev1
        prev1 = max(prev2+num, prev1)
        prev2 = temp
    }
    return prev1
}

Scala

class Solution {
  def rob(nums: Array[Int]): Int = {
    if (nums.isEmpty) return 0
    if (nums.length == 1) return nums(0)

    var prev1 = 0
    var prev2 = 0

    for (num <- nums) {
      val temp = prev1
      prev1 = Math.max(prev2 + num, prev1)
      prev2 = temp
    }

    prev1
  }
}

Kotlin

class Solution {
  fun rob(nums: IntArray): Int {
    if (nums.isEmpty()) {
      return 0
    }
    if (nums.size == 1) {
      return nums[0]
    }

    var prev1 = 0
    var prev2 = 0

    for (num in nums) {
      val temp = prev1
      prev1 = maxOf(prev2 + num, prev1)
      prev2 = temp
    }

    return prev1
  }
}

Swift

import Foundation

class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.isEmpty {
            return 0
        }
        if nums.count == 1 {
            return nums[0]
        }

        var prev1 = 0
        var prev2 = 0

        for num in nums {
            let temp = prev1
            prev1 = max(prev2 + num, prev1)
            prev2 = temp
        }

        return prev1
    }
}

Rust

impl Solution {
    pub fn rob(&self, nums: Vec<i32>) -> i32 {
        if nums.is_empty() {
            return 0;
        }
        if nums.len() == 1 {
            return nums[0];
        }

        let mut prev1 = 0;
        let mut prev2 = 0;

        for &num in nums.iter() {
            let temp = prev1;
            prev1 = prev1.max(prev2 + num);
            prev2 = temp;
        }

        prev1
    }
}

C#

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }
        if (nums.Length == 1) {
            return nums[0];
        }

        int prev1 = 0, prev2 = 0;

        foreach (int num in nums) {
            int temp = prev1;
            prev1 = Math.Max(prev2 + num, prev1);
            prev2 = temp;
        }

        return prev1;
    }
}

Dart

class Solution {
  int rob(List<int> nums) {
    if (nums.isEmpty) {
      return 0;
    }
    if (nums.length == 1) {
      return nums[0];
    }

    int prev1 = 0, prev2 = 0;

    for (int num in nums) {
      int temp = prev1;
      prev1 = (prev2 + num > prev1) ? prev2 + num : prev1;
      prev2 = temp;
    }

    return prev1;
  }
}

PHP

class Solution {
    public function rob(array $nums): int {
        if (empty($nums)) {
            return 0;
        }
        if (count($nums) === 1) {
            return $nums[0];
        }

        $prev1 = 0;
        $prev2 = 0;

        foreach ($nums as $num) {
            $temp = $prev1;
            $prev1 = max($prev2 + $num, $prev1);
            $prev2 = $temp;
        }

        return $prev1;
    }
}

Ruby

class Solution
  def rob(nums)
    return 0 if nums.nil? || nums.empty?
    return nums[0] if nums.length == 1

    prev1, prev2 = 0, 0

    nums.each do |num|
      temp = prev1
      prev1 = [prev2 + num, prev1].max
      prev2 = temp
    end

    prev1
  end
end