House Robber Solution

Problem

You have a row of houses, each containing some amount of money. You want to steal as much as possible, but you can't rob two houses that are directly next to each other — that triggers the alarm system. Return the maximum amount you can steal.

Example:

Input: nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob house 0 (2) + house 2 (9) + house 4 (1) = 12; skipping the higher-value house 1 because taking it would block house 2.

Counter-example: Greedily always taking the largest available house fails — in [2, 1, 1, 2], picking house 1 (value 1) and house 3 (value 2) gives 3, while houses 0 and 3 both give 4.

Intuition

At each house you face the same binary choice: rob it (and skip the one before) or skip it (and carry forward the best result so far). This means the answer at house i depends only on the best result two houses back plus the current value, versus the best result one house back. You only ever need the last two values, not the full history.

Approach 1 — DP Array

Build an array where dp[i] is the most money you can rob from the first i+1 houses. The recurrence at each step is: either skip house i (keep dp[i-1]) or rob it (add nums[i] to the best result two houses back).

Steps:

Handle the trivial case: if there's only one house, return its value
Initialize dp[0] = nums[0] and dp[1] = max(nums[0], nums[1])
For each remaining house i, compute dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Return dp[n-1]

1def rob(nums):
2    n = len(nums)
3    if n == 1:
4        return nums[0]
5
6    dp = [0] * n
7    dp[0] = nums[0]
8    dp[1] = max(nums[0], nums[1])  # best of robbing first or second house
9
10    for i in range(2, n):
11        # either skip house i, or rob it using the best result two steps back
12        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
13
14    return dp[-1]

Time: O(n) — single pass through the array
Space: O(n) — the DP array stores one value per house

Approach 2 — Space-Optimized DP

The recurrence only looks back two positions, so we don't need the full array — just two rolling variables. Replace dp[i-2] with prev2 and dp[i-1] with prev1, updating both in tandem each step.

Steps:

Initialize both prev2 and prev1 to 0 (representing an empty prefix)
For each house, compute current = max(prev1, prev2 + amount)
Slide the window: set prev2 = prev1, then prev1 = current
Return prev1

1def rob(nums):
2    prev2 = prev1 = 0
3    for amount in nums:
4        # compute together to avoid using the updated prev2 in the same step
5        prev2, prev1 = prev1, max(prev1, prev2 + amount)
6    return prev1

Time: O(n) — single pass through the array
Space: O(1) — only two variables regardless of input size

Complexity Summary

Approach	Time	Space	When to use
DP Array	O(n)	O(n)	When you need to reconstruct which houses were robbed, or when explaining the recurrence in an interview
Space-Optimized DP	O(n)	O(1)	Production code and interview final answer — the DP structure is simple enough that the array adds no value

Common Mistakes

Initializing dp[1] = nums[1] instead of max(nums[0], nums[1]): At index 1, the best you can do is the larger of the two houses, not just the second. This produces wrong answers on any input where nums[0] > nums[1].
Not handling the single-house edge case in the array approach: Accessing dp[1] when n == 1 causes an out-of-bounds error. The space-optimized approach avoids this because the loop simply runs once.
Sequential assignment when sliding the window: Writing prev2 = prev1; prev1 = max(prev1, prev2 + amount) uses the already-updated prev2 in the second line. Always compute the new value before reassigning, or use Python's tuple assignment.
Assuming you can only skip one house: The recurrence allows skipping multiple consecutive houses — dp[i-1] carries forward the best solution including any run of skips. In [5, 1, 1, 5], robbing houses 0 and 3 (skipping two) gives 10, and the DP reaches this correctly.
Mutating the input array as a DP table: Storing results in nums directly works for this problem but breaks the House Robber II variant where you need the original values in a second pass.

House Robber — Solution