Skip to main content
CodePeetCodePeet
CodePeet 250

House Robber

MEDIUMProblemSolveExternal Links

Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed inside. The only constraint stopping you from robbing every house is that adjacent houses have connected security systems — if two houses next to each other are both robbed on the same night, the alarm will trigger and the police will be called.

Given an integer array nums where nums[i] represents the amount of money in the i-th house, find the maximum amount of money you can rob tonight without robbing any two adjacent houses.

You need to select a subset of houses such that no two selected houses are neighbors, and the total money from the selected houses is maximized.

Examples

Example 1

Input: nums = [1, 2, 3, 1]

Output: 4

Explanation: Rob house 0 (money = 1) and house 2 (money = 3). Houses 0 and 2 are not adjacent, so no alarm is triggered. Total = 1 + 3 = 4. Robbing houses 1 and 3 would give 2 + 1 = 3, which is less. Robbing house 2 alone gives 3, and robbing houses 0, 2 gives 4, which is the maximum.

Example 2

Input: nums = [2, 7, 9, 3, 1]

Output: 12

Explanation: Rob house 0 (money = 2), house 2 (money = 9), and house 4 (money = 1). None of these are adjacent. Total = 2 + 9 + 1 = 12. Any other valid combination gives less: robbing houses 1 and 3 gives 7 + 3 = 10; robbing houses 0, 2 gives 11; robbing houses 0, 3, gives 5. The maximum is 12.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward approach is to try every possible combination of non-adjacent houses using recursion.

At each house, you have two choices: rob it or skip it. If you rob house i, you cannot rob house i+1 (the adjacent one), so your next option is house i+2. If you skip house i, you move on to house i+1.

This creates a decision tree. At house 0, you branch into two paths — rob or skip. Each path leads to more branches, and so on. At the end, you compare the total money from all possible valid paths and return the maximum.

Think of it like standing at the start of a buffet line. At each dish, you either take it and skip the next dish, or pass on it and consider the next dish. You want to maximize the total calories (money) you collect.

The problem with this approach is that many subproblems are solved repeatedly. For example, the question "what's the best I can do starting from house 3?" might be asked from multiple branches, and each time we recompute it from scratch.

Step-by-Step Explanation

Let's trace through with nums = [2, 7, 9, 3, 1]:

Step 1: Start at house 0 (money = 2). Two choices:

  • Path A: Rob house 0 → jump to house 2
  • Path B: Skip house 0 → move to house 1

Step 2 (Path A): At house 2 (money = 9). Two choices:

  • Rob house 2 → jump to house 4
  • Skip house 2 → move to house 3

Step 3 (Path A, rob 2): At house 4 (money = 1). Rob it (last house). Total from this path: 2 + 9 + 1 = 12.

Step 4 (Path A, skip 2): At house 3 (money = 3). Two choices:

  • Rob house 3 → jump to house 5 (out of bounds, done). Total: 2 + 3 = 5.
  • Skip house 3 → move to house 4. Rob house 4. Total: 2 + 1 = 3.

Step 5 (Path B): At house 1 (money = 7). Two choices, leading to many more branches...

Step 6: After exploring all branches, the maximum across all valid paths is 12.

Result: 12.

Recursive Brute Force — Exploring All Valid Combinations — Watch how the brute force explores rob-or-skip decisions at each house, building different combinations of non-adjacent houses and tracking the maximum total.

Algorithm

  1. Define a recursive function rob(i) that returns the maximum money starting from house i
  2. Base case: if i ≥ n, return 0 (no more houses)
  3. Recursive case: return max of:
    • Rob house i: nums[i] + rob(i + 2)
    • Skip house i: rob(i + 1)
  4. Call rob(0) to get the answer

Code

class Solution {
public:
    int rob(vector<int>& nums) {
        return helper(nums, 0);
    }
    
    int helper(vector<int>& nums, int i) {
        if (i >= nums.size()) return 0;
        
        int robCurrent = nums[i] + helper(nums, i + 2);
        int skipCurrent = helper(nums, i + 1);
        
        return max(robCurrent, skipCurrent);
    }
};
class Solution:
    def rob(self, nums: list[int]) -> int:
        def helper(i):
            if i >= len(nums):
                return 0
            
            rob_current = nums[i] + helper(i + 2)
            skip_current = helper(i + 1)
            
            return max(rob_current, skip_current)
        
        return helper(0)
class Solution {
    public int rob(int[] nums) {
        return helper(nums, 0);
    }
    
    private int helper(int[] nums, int i) {
        if (i >= nums.length) return 0;
        
        int robCurrent = nums[i] + helper(nums, i + 2);
        int skipCurrent = helper(nums, i + 1);
        
        return Math.max(robCurrent, skipCurrent);
    }
}

Complexity Analysis

Time Complexity: O(2ⁿ)

At each house, we branch into two recursive calls (rob or skip). This creates a binary decision tree with up to 2ⁿ leaves. Many subproblems are recomputed — for example, helper(3) might be called from both helper(1) and helper(2).

Space Complexity: O(n)

The recursion stack goes at most n levels deep (one level per house in the worst case). No additional data structures are used.

Why This Approach Is Not Efficient

The brute force recursion has O(2ⁿ) time complexity because it recomputes the same subproblems many times. For example, with 5 houses, helper(3) ("what's the best from house 3 onward?") is computed both when we skip house 2 and when we rob house 1. With 100 houses (the constraint limit), 2¹⁰⁰ is astronomically large — the solution would never finish.

The key observation is that this problem has overlapping subproblems and optimal substructure — the hallmarks of Dynamic Programming. The answer for "best robbery starting at house i" only depends on the answers for houses i+1 and i+2, and these answers don't change no matter which path led us to house i.

By storing (memoizing) the result for each subproblem, we avoid recomputation entirely. Better yet, we can build the solution iteratively from the bottom up using a DP table.

Better Approach - Dynamic Programming with Array

Intuition

Instead of recursion, we can solve this bottom-up using dynamic programming.

Define dp[i] as the maximum money we can rob from houses 0 through i. At each house i, we face the same two choices:

  1. Rob house i: We take nums[i], but we cannot rob house i-1. So the best we can do is nums[i] + dp[i-2] (the best from houses 0 through i-2).
  2. Skip house i: We don't rob house i, so the best is dp[i-1] (the best from houses 0 through i-1).

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

Think of it like a game show where you walk down a line of prizes. At each prize, you decide: "Is this prize plus the best I could do two steps back better than the best I could do one step back (without this prize)?" You keep a running record of the best total at each position.

We fill the dp array from left to right. The answer is dp[n-1] — the best we can do considering all houses.

Step-by-Step Explanation

Let's trace through with nums = [2, 7, 9, 3, 1]:

Step 1: Initialize dp array of size 5. dp[0] = nums[0] = 2 (only one house to consider).

Step 2: dp[1] = max(nums[0], nums[1]) = max(2, 7) = 7. With two houses, we pick the richer one.

Step 3: i = 2. dp[2] = max(dp[1], nums[2] + dp[0]) = max(7, 9 + 2) = max(7, 11) = 11.

  • Robbing house 2 (9)+bestfromhouses0..0(9) + best from houses 0..0 (2) = 11beatsskippinghouse2(11 beats skipping house 2 (7).

Step 4: i = 3. dp[3] = max(dp[2], nums[3] + dp[1]) = max(11, 3 + 7) = max(11, 10) = 11.

  • Robbing house 3 (3)+bestfromhouses0..1(3) + best from houses 0..1 (7) = 10.Skippinghouse3(10. Skipping house 3 (11) is better.

Step 5: i = 4. dp[4] = max(dp[3], nums[4] + dp[2]) = max(11, 1 + 11) = max(11, 12) = 12.

  • Robbing house 4 (1)+bestfromhouses0..2(1) + best from houses 0..2 (11) = 12beatsskipping(12 beats skipping (11).

Result: dp[4] = 12.

Bottom-Up DP — Building the Optimal Solution — Watch how we fill the dp table left to right. At each position, we choose the maximum of skipping the current house (dp[i-1]) or robbing it (nums[i] + dp[i-2]).

Algorithm

  1. If there's only one house, return nums[0]
  2. Create a dp array of size n
  3. dp[0] = nums[0]
  4. dp[1] = max(nums[0], nums[1])
  5. For i from 2 to n-1:
    • dp[i] = max(dp[i-1], nums[i] + dp[i-2])
  6. Return dp[n-1]

Code

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        
        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        
        return dp[n - 1];
    }
};
class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        for i in range(2, n):
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
        
        return dp[n - 1]
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        
        return dp[n - 1];
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array once, computing dp[i] in O(1) at each step. Total: n iterations × O(1) = O(n).

Space Complexity: O(n)

We use a dp array of size n to store intermediate results. This is a massive improvement from the O(2ⁿ) brute force, but we can still optimize the space.

Why This Approach Is Not Efficient

The DP array approach runs in O(n) time, which is optimal — we must look at every house at least once. However, it uses O(n) space for the dp array.

Looking at the recurrence dp[i] = max(dp[i-1], nums[i] + dp[i-2]), we see that each dp[i] depends only on the previous two values: dp[i-1] and dp[i-2]. We never look further back than two positions.

This means we don't need to store the entire dp array — just the last two values. By keeping two variables (prev1 and prev2) instead of an array, we reduce space from O(n) to O(1) while maintaining the same O(n) time complexity.

This is a common optimization pattern in DP: when the recurrence only depends on a fixed window of previous states, you can replace the array with a constant number of variables.

Optimal Approach - Space-Optimized DP

Intuition

The recurrence dp[i] = max(dp[i-1], nums[i] + dp[i-2]) only looks at the two most recent dp values. So instead of maintaining an entire array, we keep just two variables:

  • prev1: the maximum money from all houses up to and including the previous house (dp[i-1])
  • prev2: the maximum money from all houses up to and including the house before the previous one (dp[i-2])

At each step, we compute the new maximum as max(prev1, nums[i] + prev2), then shift the variables forward: prev2 becomes prev1, and prev1 becomes the newly computed value.

Think of it like a caterpillar walking along a branch. The caterpillar only needs its two back legs to know where it's been — it doesn't need to remember every position it's ever touched. Similarly, our algorithm only needs the last two DP values to make the optimal decision at each house.

This gives us the same O(n) time with O(1) space — the true optimal solution.

Step-by-Step Explanation

Let's trace through with nums = [2, 7, 9, 3, 1]:

Step 1: Initialize prev2 = 0 (no houses before house 0), prev1 = 0 (nothing processed yet).

Step 2: i = 0, nums[0] = 2. current = max(prev1, nums[0] + prev2) = max(0, 2 + 0) = 2. Shift: prev2 = 0, prev1 = 2.

Step 3: i = 1, nums[1] = 7. current = max(prev1, nums[1] + prev2) = max(2, 7 + 0) = 7. Shift: prev2 = 2, prev1 = 7.

Step 4: i = 2, nums[2] = 9. current = max(prev1, nums[2] + prev2) = max(7, 9 + 2) = 11. Shift: prev2 = 7, prev1 = 11.

Step 5: i = 3, nums[3] = 3. current = max(prev1, nums[3] + prev2) = max(11, 3 + 7) = 11. Shift: prev2 = 11, prev1 = 11.

Step 6: i = 4, nums[4] = 1. current = max(prev1, nums[4] + prev2) = max(11, 1 + 11) = 12. Shift: prev2 = 11, prev1 = 12.

Result: prev1 = 12.

Space-Optimized DP — Two Variables Replace the Array — Watch how prev1 and prev2 slide forward through the houses, carrying just enough history to make the optimal rob-or-skip decision at each step, using O(1) space.

Algorithm

  1. If there's only one house, return nums[0]
  2. Initialize prev2 = 0, prev1 = 0
  3. For each house i from 0 to n-1:
    a. current = max(prev1, nums[i] + prev2)
    b. prev2 = prev1
    c. prev1 = current
  4. Return prev1

Code

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0, prev1 = 0;
        
        for (int num : nums) {
            int current = max(prev1, num + prev2);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
};
class Solution:
    def rob(self, nums: list[int]) -> int:
        prev2 = 0
        prev1 = 0
        
        for num in nums:
            current = max(prev1, num + prev2)
            prev2 = prev1
            prev1 = current
        
        return prev1
class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        
        for (int num : nums) {
            int current = Math.max(prev1, num + prev2);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array once, performing O(1) work at each step (one max comparison, two variable assignments). Total: O(n).

Space Complexity: O(1)

We use only three variables (prev2, prev1, current) regardless of input size. No arrays, no hash maps, no recursion stack. This is the optimal space complexity — we cannot solve the problem without at least reading the input.

This solution is optimal in both time and space. The time is O(n) because we must examine every house at least once. The space is O(1) because the recurrence depends on only the last two values. No further optimization is possible.