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 handlinglen(nums) < 3naturally 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
iandjwhere|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 mosti-2(sincei-1is adjacent). The value becomesnums[i] + max_money(i-2). - If I skip house
i, my total money remains what I could get from houses up toi-1.
This gives us the recurrence relation: .
A naive recursive solution would explore a tree of possibilities, leading to exponential time complexity () 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 stores max money up to house i, I only need the results from the previous two steps:
prev2: Max money robbed ending at or before indexi-2.prev1: Max money robbed ending at or before indexi-1.
In each iteration, I calculate the current max (current) and then shift my window:
- The new
prev2becomes the oldprev1. - The new
prev1becomes the calculatedcurrent.
This allows us to solve it in a single pass.
Complexity Analysis
- Time: , where is the number of houses. We iterate through the array exactly once performing constant-time math operations per house.
- Space: . 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).
- Iteration 1:
- 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.