← Back to DevBytes
Developer Tutorial July 10, 2026 14 min read

House Robber Problem: Multiple Solutions and Complexity Analysis

Introduction to the House Robber Problem

The House Robber problem is a classic dynamic programming challenge that appears frequently in coding interviews and competitive programming platforms like LeetCode. It serves as an excellent introduction to optimization problems where decisions have cascading constraints.

At its core, the problem asks: given an array of non-negative integers representing the amount of money stashed in each house along a street, determine the maximum amount of money you can rob tonight without triggering an alarm. The alarm triggers if two adjacent houses are robbed on the same night. You must find the optimal subset of non-adjacent houses that yields the maximum sum.

Problem Statement (Formal Definition)

Given an integer array nums where nums[i] represents the money in house i, return the maximum sum achievable by selecting a subset of indices such that no two selected indices are adjacent. For example:

Input: nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob house 0 (2) + house 2 (9) + house 4 (1) = 12

Input: nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 0 (1) + house 2 (3) = 4

Input: nums = [2, 1, 1, 2]
Output: 4
Explanation: Rob house 0 (2) + house 3 (2) = 4

Why This Problem Matters

The House Robber problem is more than an interview puzzle — it's a gateway to understanding dynamic programming patterns that recur across countless optimization problems. Here's why it's essential:

Solution 1: Naive Recursion (Brute Force)

🚀 Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

The most intuitive approach mimics human decision-making: at each house, you either rob it (and skip the next) or skip it (and move to the next). This generates all possible combinations and selects the maximum sum.

Recursive Decision Tree

For each house at index i, you have two choices:

The recurrence relation emerges as:

rob(i) = max( nums[i] + rob(i+2), rob(i+1) )

Implementation

def rob_brute_force(nums):
    """
    Naive recursive solution without memoization.
    Time Complexity: O(2^n) - exponential
    Space Complexity: O(n) - recursion stack depth
    """
    n = len(nums)
    
    def recurse(i):
        # Base case: past the last house
        if i >= n:
            return 0
        
        # Option 1: rob current house, skip next
        rob_current = nums[i] + recurse(i + 2)
        
        # Option 2: skip current house
        skip_current = recurse(i + 1)
        
        return max(rob_current, skip_current)
    
    return recurse(0)


# Test the function
nums = [2, 7, 9, 3, 1]
print(rob_brute_force(nums))  # Output: 12

Complexity Analysis

The exponential time complexity makes this solution impractical for arrays larger than about 30 elements. The overlapping subproblems — where recurse(3) might be called from both recurse(1) (rob then skip) and recurse(2) (skip then skip) — beg for optimization.

Solution 2: Top-Down Dynamic Programming (Memoization)

Memoization caches the results of expensive recursive calls. Since the function recurse(i) is deterministic — given the same i and the same input array, it always returns the same value — we can store results in a dictionary or array and retrieve them instantly on subsequent calls.

How Memoization Eliminates Redundant Work

The recursion tree collapses from exponential to linear because each subproblem recurse(i) is computed exactly once. Once computed, any future request for recurse(i) returns the cached value in O(1) time.

Implementation

def rob_memoization(nums):
    """
    Top-down DP with memoization using an array cache.
    Time Complexity: O(n)
    Space Complexity: O(n) - memo array + recursion stack
    """
    n = len(nums)
    memo = [-1] * n  # -1 indicates uncomputed
    
    def recurse(i):
        # Base case: out of bounds
        if i >= n:
            return 0
        
        # Return cached result if already computed
        if memo[i] != -1:
            return memo[i]
        
        # Option 1: rob current house, recurse on i+2
        rob_current = nums[i] + recurse(i + 2)
        
        # Option 2: skip current house, recurse on i+1
        skip_current = recurse(i + 1)
        
        # Cache the best decision for this position
        memo[i] = max(rob_current, skip_current)
        return memo[i]
    
    return recurse(0)


# Test the function
nums = [2, 7, 9, 3, 1]
print(rob_memoization(nums))  # Output: 12

# Larger test to demonstrate efficiency
import random
large_nums = [random.randint(1, 100) for _ in range(100)]
print(rob_memoization(large_nums))  # Computes instantly

Tracing the Memoized Solution

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

recurse(0):
  memo[0] not computed
  rob_current = 2 + recurse(2)    [needs recurse(2)]
  skip_current = recurse(1)       [needs recurse(1)]

recurse(1):
  memo[1] not computed
  rob_current = 7 + recurse(3)    [needs recurse(3)]
  skip_current = recurse(2)       [needs recurse(2)]

recurse(3):
  memo[3] not computed
  rob_current = 3 + recurse(5)    [recurse(5) returns 0]
  skip_current = recurse(4)       [needs recurse(4)]
  
recurse(4):
  memo[4] not computed
  rob_current = 1 + recurse(6)    [recurse(6) returns 0]
  skip_current = recurse(5)       [recurse(5) returns 0]
  memo[4] = max(1, 0) = 1
  returns 1

  back in recurse(3):
  rob_current = 3 + 0 = 3
  skip_current = 1
  memo[3] = max(3, 1) = 3
  returns 3

recurse(2):
  memo[2] not computed
  rob_current = 9 + recurse(4)    [recurse(4) cached = 1]
  skip_current = recurse(3)       [recurse(3) cached = 3]
  memo[2] = max(10, 3) = 10
  returns 10

  back in recurse(1):
  rob_current = 7 + 3 = 10
  skip_current = 10
  memo[1] = max(10, 10) = 10
  returns 10

  back in recurse(0):
  rob_current = 2 + 10 = 12
  skip_current = 10
  memo[0] = max(12, 10) = 12
  returns 12

Complexity Analysis

Solution 3: Bottom-Up Dynamic Programming (Tabulation)

Bottom-up DP flips the perspective: instead of starting from the first house and recursing forward, we build the solution from the end backward. This eliminates recursion overhead entirely and makes the dependencies crystal clear.

The Intuition Behind Bottom-Up

Define dp[i] as the maximum amount you can rob from houses i through n-1 (the suffix starting at index i). The recurrence remains the same, but we compute it iteratively from right to left:

dp[i] = max( nums[i] + dp[i+2], dp[i+1] )

We need base cases for indices beyond the array bounds. A common trick is to pad the DP array with extra elements initialized to 0.

Implementation

def rob_bottom_up_array(nums):
    """
    Bottom-up DP using a full DP array.
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    n = len(nums)
    
    # Handle edge cases
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    
    # dp[i] = max rob from house i to end
    # We'll pad with two extra elements for i+2 access
    dp = [0] * (n + 2)  # indices 0..n-1 for houses, n and n+1 are sentinel zeros
    
    # Fill from right to left
    for i in range(n - 1, -1, -1):
        rob_current = nums[i] + dp[i + 2]
        skip_current = dp[i + 1]
        dp[i] = max(rob_current, skip_current)
    
    return dp[0]


# Alternative: forward iteration (left to right)
def rob_bottom_up_forward(nums):
    """
    Bottom-up DP iterating from left to right.
    dp[i] represents the max rob up to house i (inclusive).
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    n = len(nums)
    
    if n == 0:
        return 0
    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):
        # Either skip house i (take dp[i-1]) or rob it (add nums[i] to dp[i-2])
        dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
    
    return dp[-1]


# Test both
nums = [2, 7, 9, 3, 1]
print(rob_bottom_up_array(nums))     # Output: 12
print(rob_bottom_up_forward(nums))   # Output: 12

Step-by-Step Trace (Forward Approach)

Using nums = [2, 7, 9, 3, 1] with the forward DP:

Initialization:
  dp[0] = nums[0] = 2
  dp[1] = max(nums[0], nums[1]) = max(2, 7) = 7

i = 2 (house with 9):
  dp[2] = max(dp[1], nums[2] + dp[0])
         = max(7, 9 + 2) = max(7, 11) = 11

i = 3 (house with 3):
  dp[3] = max(dp[2], nums[3] + dp[1])
         = max(11, 3 + 7) = max(11, 10) = 11

i = 4 (house with 1):
  dp[4] = max(dp[3], nums[4] + dp[2])
         = max(11, 1 + 11) = max(11, 12) = 12

Return dp[4] = 12

Complexity Analysis

Solution 4: Space-Optimized DP (Two Variables)

Observing the recurrence, we notice that dp[i] depends only on dp[i+1] and dp[i+2]. We don't need the entire array — just two variables tracking the previous two results.

The Optimization Insight

This is a classic Fibonacci-like pattern. Instead of maintaining an array, we keep two variables rolling forward (or backward). This reduces space complexity from O(n) to O(1) while maintaining the O(n) time complexity.

Implementation (Right-to-Left)

def rob_space_optimized_rl(nums):
    """
    Space-optimized DP iterating from right to left.
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    n = len(nums)
    
    # prev1 = dp[i+1], prev2 = dp[i+2]
    # Initialize as 0 (beyond the array)
    prev1 = 0  # represents rob from i+1 to end
    prev2 = 0  # represents rob from i+2 to end
    
    # Iterate from rightmost house to leftmost
    for i in range(n - 1, -1, -1):
        # Current best = max(rob this + two houses away result, skip this)
        current = max(nums[i] + prev2, prev1)
        
        # Shift: prev2 becomes prev1, prev1 becomes current
        prev2 = prev1
        prev1 = current
    
    return prev1


nums = [2, 7, 9, 3, 1]
print(rob_space_optimized_rl(nums))  # Output: 12

Implementation (Left-to-Right)

def rob_space_optimized_lr(nums):
    """
    Space-optimized DP iterating from left to right.
    This is often the most intuitive version.
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    n = len(nums)
    
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    
    # Two variables tracking the max up to previous houses
    two_back = nums[0]                        # max up to house 0
    one_back = max(nums[0], nums[1])          # max up to house 1
    
    for i in range(2, n):
        # Max between skipping (one_back) or robbing (nums[i] + two_back)
        current = max(one_back, nums[i] + two_back)
        
        # Shift variables for next iteration
        two_back = one_back
        one_back = current
    
    return one_back


nums = [2, 7, 9, 3, 1]
print(rob_space_optimized_lr(nums))  # Output: 12

# Edge case tests
print(rob_space_optimized_lr([]))       # 0
print(rob_space_optimized_lr([5]))      # 5
print(rob_space_optimized_lr([2, 1]))   # 2 (rob only house 0)
print(rob_space_optimized_lr([1, 2]))   # 2 (rob only house 1)

Detailed Trace of Left-to-Right Version

Let's trace [2, 7, 9, 3, 1]:

Initialize:
  two_back = nums[0] = 2
  one_back = max(2, 7) = 7

i = 2 (value 9):
  current = max(one_back, nums[2] + two_back)
          = max(7, 9 + 2) = max(7, 11) = 11
  two_back = 7
  one_back = 11

i = 3 (value 3):
  current = max(11, 3 + 7) = max(11, 10) = 11
  two_back = 11
  one_back = 11

i = 4 (value 1):
  current = max(11, 1 + 11) = max(11, 12) = 12
  two_back = 11
  one_back = 12

Return one_back = 12

Complexity Analysis

Comprehensive Comparison Table

Here's a side-by-side summary of all four approaches:

┌────────────────────┬────────────────┬──────────────┬──────────────┐
│ Approach           │ Time           │ Space        │ Use Case      │
├────────────────────┼────────────────┼──────────────┼──────────────┤
│ Naive Recursion    │ O(2^n)         │ O(n) stack   │ n ≤ 25 only   │
│ Memoization (TD)   │ O(n)           │ O(n)         │ Clean, clear  │
│ Bottom-Up Array    │ O(n)           │ O(n)         │ No recursion  │
│ Two Variables      │ O(n)           │ O(1) ★       │ Production    │
└────────────────────┴────────────────┴──────────────┴──────────────┘

Extension: House Robber II (Circular Houses)

A common follow-up in interviews arranges the houses in a circle. The first and last houses become adjacent, so you cannot rob both. The solution elegantly reuses the linear House Robber logic: compute the maximum for two slices — one excluding the first house, one excluding the last — and take the maximum of the two.

def rob_circular(nums):
    """
    House Robber II: circular street.
    Strategy: run the linear algorithm on nums[1:] and nums[:-1]
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    n = len(nums)
    
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    
    def rob_linear(arr):
        if len(arr) == 0:
            return 0
        if len(arr) == 1:
            return arr[0]
        
        two_back = arr[0]
        one_back = max(arr[0], arr[1])
        
        for i in range(2, len(arr)):
            current = max(one_back, arr[i] + two_back)
            two_back = one_back
            one_back = current
        
        return one_back
    
    # Case 1: exclude last house (rob from 0 to n-2)
    max1 = rob_linear(nums[:-1])
    
    # Case 2: exclude first house (rob from 1 to n-1)
    max2 = rob_linear(nums[1:])
    
    return max(max1, max2)


# Test
print(rob_circular([2, 3, 2]))        # Output: 3 (rob house 1 only)
print(rob_circular([1, 2, 3, 1]))     # Output: 4 (rob house 1 and 3)
print(rob_circular([1, 2, 3]))        # Output: 3

Best Practices and Interview Tips

1. Start Simple, Then Optimize

When solving in an interview, begin by stating the brute-force recursive approach. This demonstrates you understand the problem's structure. Then identify overlapping subproblems and introduce memoization. Finally, convert to bottom-up and then space-optimize. This progression shows systematic thinking.

2. Define Your DP State Clearly

Whether you choose dp[i] as "max from i to end" or "max from start to i," be explicit. Write the recurrence relation on the board before coding. Ambiguity about what dp[i] represents is a common source of off-by-one errors.

3. Handle Edge Cases First

Always handle n == 0 (empty array) and n == 1 (single house) explicitly at the top of your function. This prevents index-out-of-bounds errors and makes the main algorithm cleaner.

4. Use Descriptive Variable Names in the Space-Optimized Version

Names like prev1 and prev2 are common but can be confusing. Consider one_back and two_back or rob_prev and rob_prev2. Clarity matters more than brevity in interview settings.

5. Test With Small, Edge, and Random Cases

Verify your solution against:

6. Recognize the Pattern for Related Problems

The "can't pick adjacent" constraint appears in multiple guises. Problems like Delete and Earn (LeetCode 740) reduce to House Robber after preprocessing. The pattern also appears in Maximum Sum of Non-Adjacent Elements in a Circular Array and Paint House variations. Building intuition here pays dividends across the DP landscape.

Complete Test Suite

Here's a comprehensive test harness you can use to validate all implementations:

def test_all_implementations():
    """
    Runs all House Robber implementations against
    a battery of test cases and reports results.
    """
    implementations = [
        ("Brute Force", rob_brute_force),
        ("Memoization", rob_memoization),
        ("Bottom-Up Array", rob_bottom_up_forward),
        ("Space-Optimized LR", rob_space_optimized_lr),
        ("Space-Optimized RL", rob_space_optimized_rl),
    ]
    
    test_cases = [
        ([], 0),
        ([5], 5),
        ([2, 1], 2),
        ([1, 2], 2),
        ([2, 7, 9, 3, 1], 12),
        ([1, 2, 3, 1], 4),
        ([2, 1, 1, 2], 4),
        ([4, 4, 4, 4], 8),
        ([1, 2, 3, 4, 5], 9),
        ([10, 1, 1, 10], 20),
        ([5, 1, 2, 10, 6], 17),  # rob 5, 10 = 15? or 5, 2, 6 = 13? or 1, 10 = 11
    ]
    
    all_passed = True
    for name, func in implementations:
        passed = True
        for nums, expected in test_cases:
            result = func(nums)
            if result != expected:
                print(f"[FAIL] {name}: nums={nums} -> got {result}, expected {expected}")
                passed = False
                all_passed = False
        if passed:
            print(f"[PASS] {name}: all {len(test_cases)} test cases passed")
    
    return all_passed

# Run the tests
test_all_implementations()

Conclusion

The House Robber problem is a quintessential dynamic programming exercise that progresses naturally from exponential brute force to linear time with constant space. By mastering all four solution approaches — naive recursion, memoization, bottom-up tabulation, and two-variable optimization — you internalize the complete DP problem-solving workflow. The recurrence dp[i] = max(nums[i] + dp[i+2], dp[i+1]) captures the core insight: optimal decisions depend on optimal solutions to adjacent subproblems. This pattern recurs throughout algorithm design, from resource allocation to graph problems. The space-optimized O(1) solution stands as a testament that DP doesn't always require full tables — sometimes two variables suffice. Whether you're preparing for technical interviews or building production systems, the House Robber problem equips you with a mental framework for tackling constrained optimization challenges with confidence and clarity.

🚀 Need a reliable AI agent for your project?

Deploy Hermes Agent in 10 minutes. Managed hosting, zero DevOps.

Get Started — $23.99/mo
← Back to all articles