224. House Robber

Why this mechanism works

For the current house, every legal optimum either skips it or takes it. Skipping preserves the best answer through the previous house. Taking excludes that previous house and adds the current value to the best through two positions back. These alternatives describe complete legal selections, not just local value comparisons.

State and boundaries

previous is the best for the prefix excluding the most recent house; current is the best for the entire processed prefix.

Protocol

1. Initialize both empty-prefix states to zero.
2. Compute max(current,previous+value) for each house.
3. Roll previous to old current and current to the new optimum.
4. Return current.

Visualization

[2,7,9,3,1]
prefix best: 2,7,11,11,12
final selection indices 0,2,4 gives 2+9+1=12

Python implementation

def rob_houses(nums):
    previous = current = 0
    for value in nums:
        previous, current = current, max(current, previous + value)
    return current

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 rob_houses: previous = current = 0
nums=[2, 7, 9, 3, 1]; previous=0; current=0

L3 rob_houses: for value in nums:
nums=[2, 7, 9, 3, 1]; previous=0; current=0; value=2

L4 rob_houses: previous, current = current, max(current, previous + value)
nums=[2, 7, 9, 3, 1]; previous=0; current=2; value=2

L3 rob_houses: for value in nums:
nums=[2, 7, 9, 3, 1]; previous=0; current=2; value=7

L4 rob_houses: previous, current = current, max(current, previous + value)
nums=[2, 7, 9, 3, 1]; previous=2; current=7; value=7

L3 rob_houses: for value in nums:
nums=[2, 7, 9, 3, 1]; previous=2; current=7; value=9

L4 rob_houses: previous, current = current, max(current, previous + value)
nums=[2, 7, 9, 3, 1]; previous=7; current=11; value=9

L3 rob_houses: for value in nums:
nums=[2, 7, 9, 3, 1]; previous=7; current=11; value=3

L4 rob_houses: previous, current = current, max(current, previous + value)
nums=[2, 7, 9, 3, 1]; previous=11; current=11; value=3

L3 rob_houses: for value in nums:
nums=[2, 7, 9, 3, 1]; previous=11; current=11; value=1

L4 rob_houses: previous, current = current, max(current, previous + value)
nums=[2, 7, 9, 3, 1]; previous=11; current=12; value=1

L2 rob_houses: previous = current = 0
nums=[]; previous=0; current=0

Why the solution is correct

Partition legal selections by whether they include the current house. The skip and take recurrences give the optimum within each class, and their maximum gives the optimum over the full prefix. The zero bases allow the first house and the empty selection correctly.

Time and space

O(n) time and O(1) auxiliary state.

Common mistakes

Choosing the locally largest house can block two smaller houses whose sum is larger. Updating previous too early can permit adjacent selections.

Reasoning card

Transfer exercise

Allow negative values and require at least one house. Identify which base cases and state meanings must change.