House Robber

Problem Description

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 are 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.

Examples

Constraints

• 1 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 400

Choosing to Rob the Current House or Pass

For each house i, you have a binary decision:

1. Rob it: You get the money nums[i], but you cannot rob house i - 1. Your total money is nums[i] + max_money_robbed(i - 2).
2. Skip it: You do not get nums[i]. Your total money is max_money_robbed(i - 1).

This gives us the recurrence relationship: dp[i] = max(nums[i] + dp[i - 2], dp[i - 1]).

To solve this in O(n) time, we compute values from left to right. Because the state transition only depends on the previous two results, we can optimize space to O(1) by maintaining only two variables during the iteration.

Solution 1: Dynamic Programming (Bottom-Up, Constant Space)

Iterate through the houses, tracking the maximum money robbed from the previous two steps.

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

        int robPrev2 = 0; // max money if we stopped 2 houses ago
        int robPrev1 = 0; // max money if we stopped 1 house ago

        for (int num : nums) {
            int current = Math.max(num + robPrev2, robPrev1);
            // shift states
            robPrev2 = robPrev1;
            robPrev1 = current;
        }
        return robPrev1;
    }
}

class Solution:
    def rob(self, nums: list[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        rob_prev2 = 0  # max money if we stopped 2 houses ago
        rob_prev1 = 0  # max money if we stopped 1 house ago

        for num in nums:
            current = max(num + rob_prev2, rob_prev1)
            # shift states
            rob_prev2 = rob_prev1
            rob_prev1 = current

        return rob_prev1

#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 robPrev2 = 0; // max money if we stopped 2 houses ago
        int robPrev1 = 0; // max money if we stopped 1 house ago

        for (int num : nums) {
            int current = std::max(num + robPrev2, robPrev1);
            // shift states
            robPrev2 = robPrev1;
            robPrev1 = current;
        }
        return robPrev1;
    }
};

Complexity Analysis:

• Time Complexity: O(n). We scan the array once.
• Space Complexity: O(1). Only two tracking variables.

Where it breaks: Nothing breaks for standard arrays. If the houses are arranged in a circle (meaning the first and last houses are adjacent), this logic fails because it does not prevent robbing both endpoints. This variant requires the “House Robber II” solution.

Common Mistakes

• Incorrectly initializing state variables. Verify that your initial values do not cause off-by-one errors on single or two-house inputs.
• Modifying the input array in-place without checking constraints. While mutating nums to store DP values is possible, it violates best practices if the input array is const or shared.
• Using a full O(n) array when O(1) space is requested. Interviewers will look for the state variable reduction optimization.

Frequently Asked Questions

What happens if all house values are 0? The loops will evaluate 0 + 0 and return 0, which is correct.

How does this problem extend to a circular layout? If the street is a circle (House Robber II), you run the same O(1) algorithm twice: once on nums[0..n-2] (excluding the last house) and once on nums[1..n-1] (excluding the first house). The answer is the maximum of both runs.

What does this problem test in interviews? It tests your capability to write simple 1D dynamic programming solutions, recognize state transition dependencies, and reduce space complexity.

← All Problems