Domain 2MediumCORE

House Robber

We need to calculate the maximum sum of money we can steal from a row of houses, subject to one constraint: if we rob house i, we cannot rob house i-1 or i+1.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming

198. House Robber

Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 43.1%


Problem Breakdown

We need to calculate the maximum sum of money we can steal from a row of houses, subject to one constraint: if we rob house i, we cannot rob house i-1 or i+1.

Inputs: An integer array nums where each element represents the value in that specific house. Output: A single integer representing the maximum total money possible.

Constraints & Edge Cases to Consider:

  • Length: The problem states length is between 1 and 100, so we don’t need to handle empty arrays (nums = []), but handling len(nums) < 3 naturally simplifies our logic without special branching inside the loop.
  • Values: Non-negative integers (0 to 400). No negative values mean money is always additive; no overflow issues with standard integer types given these constraints.
  • Adjacency: The core constraint prevents selecting indices i and j where |i - j| == 1.

Intuition

If I were to approach this recursively, for every house i, I would have two choices: either rob it or skip it.

  • If I rob house i, the previous robbed house must be at most i-2 (since i-1 is adjacent). The value becomes nums[i] + max_money(i-2).
  • If I skip house i, my total money remains what I could get from houses up to i-1.

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

A naive recursive solution would explore a tree of possibilities, leading to exponential time complexity (O(2n)O(2^n)) because it recalculates results for subproblems like “maximum money from houses 0 through k” multiple times. Since the decision at house i only depends on the optimal solutions for ranges ending at i-1 and i-2, we can use Dynamic Programming to store these intermediate states, reducing complexity significantly.

Approach

I will implement this using an iterative approach with space optimization. Instead of maintaining a full DP array where dp[i]dp[i] stores max money up to house i, I only need the results from the previous two steps:

  1. prev2: Max money robbed ending at or before index i-2.
  2. prev1: Max money robbed ending at or before index i-1.

In each iteration, I calculate the current max (current) and then shift my window:

  • The new prev2 becomes the old prev1.
  • The new prev1 becomes the calculated current.

This allows us to solve it in a single pass.

Complexity Analysis

  • Time: O(n)O(n), where nn is the number of houses. We iterate through the array exactly once performing constant-time math operations per house.
  • Space: O(1)O(1). By using two variables (prev1, prev2) instead of an auxiliary array to store DP states, we achieve constant space complexity regardless of input size.

Solution

def rob(nums):
    # Handle edge case where there are no houses (though constraints say len >= 1)
    if not nums:
        return 0
    
    prev2 = 0          # Represents max money up to i-2
    prev1 = 0          # Represents max money up to i-1
    
    for num in nums:
        current = max(prev1, prev2 + num)
        
        # Shift window forward
        prev2 = prev1
        prev1 = current
        
    return prev1

# Example usage matching problem description
print(rob([1, 2, 3, 1]))      # Output: 4
print(rob([2, 7, 9, 3, 1]))   # Output: 12

Edge Cases Handled

  • Single House ([5]): The loop runs once. current = max(0, 0 + 5) = 5. Returns 5 correctly.
  • Two Houses ([2, 7]):
    • Iteration 1: prev1=2, prev2=0.
    • Iteration 2: current=max(2, 0+7)=7. Updates to return 7 (correctly skipping the first house).
  • All Zeros ([0, 0]): Logic holds; returns 0.
  • Large Values: Python handles arbitrary precision integers automatically, so sums exceeding standard integer limits are not an issue here given constraints anyway.