House Robber

Learning goal: Translate the no-adjacent-houses rule into a maximization problem.

Core idea Every house creates a decision: skip it or rob it. Robbing house i prevents robbing house i - 1, but it still allows every choice made through house i - 2. The goal is not to maximize the number of houses robbed; it is to maximize their total value.

What must be optimized

For nums = [2, 7, 9, 3, 1], taking houses with values 2, 9, and 1 gives 12. The tempting choice of taking the first, third, and fifth houses happens to work here, but parity is not a valid strategy in general.

Algorithm plan

• Process houses from left to right.
• At each position, compare skipping and robbing.
• Keep only the previous two optimal totals.
• Return the best total after the final house.

Micro-example

• Houses [2, 7]: skip 7 for 2, or rob 7 for 7.
• The best total so far is 7.

Pitfalls

• Do not assume houses with even or odd indices are best.
• Do not add adjacent values together.
• Remember that a house may contain 0.

Recap

• Each house is a skip-or-take decision.
• The no-adjacent rule determines which earlier result is compatible.
• We seek the maximum total, not a fixed pattern of indices.

Learning goal: Understand why the recurrence captures every valid robbery plan.

Core idea Let best(i) be the maximum money obtainable from houses 0 through i. If we skip house i, the result is best(i - 1). If we rob it, house i - 1 must be skipped, so the compatible result is best(i - 2) + nums[i]. Taking the larger value gives the optimal answer for the prefix ending at i.

Recurrence

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

Base cases

• Before processing any house, the total is 0.
• After the first house, the best total is nums[0].
• From there, each state depends only on the previous two states.

Micro-example For house value 9, suppose the previous totals are 7 and 2. Skipping gives 7; robbing gives 2 + 9 = 11. Therefore the new best total is 11.

Pitfalls

• best(i - 2) is required when taking a house; best(i - 1) could include its neighbor.
• The recurrence compares totals, not individual house values.
• A local choice that looks largest may block a better later combination.

Recap

• best(i) describes an entire prefix.
• The two branches are skip and take.
• The recurrence enforces non-adjacency automatically.

Learning goal: Convert the two-dimensional-looking recurrence into an O(1)-space algorithm.

Core idea The recurrence refers only to the two previous results. There is no need to store the entire best array: keep the result two positions back and the result one position back, compute the new value, then shift the variables forward.

Algorithm plan

• Initialize twoBack = 0 and oneBack = 0.
• For each value money in nums:
  • Compute current = max(oneBack, twoBack + money).
  • Move twoBack to the old oneBack.
  • Move oneBack to current.
• Return oneBack.

twoBack, oneBack = 0, 0
for money in nums:
    current = max(oneBack, twoBack + money)
    twoBack, oneBack = oneBack, current
return oneBack

Micro-example For money = 9, if twoBack = 2 and oneBack = 7, compare 7 with 2 + 9 = 11. Store 11 as the new oneBack.

Pitfalls

• Compute current before overwriting either previous total.
• Shift in the correct order: old oneBack becomes new twoBack.
• Return the latest optimum, not the last house's value.

Recap

• Only two prior DP values are needed.
• Each loop iteration performs constant work.
• The rolling update achieves O(n) time and O(1) extra space.

Learning goal: Trace the rolling variables through one complete example.

Core idea We process nums = [2, 7, 9, 3, 1] from left to right. Before each iteration, twoBack represents the best total through the house two positions earlier, while oneBack represents the best total through the immediately preceding house. The new state is the better of skipping or taking the current house.

State transitions

Micro-example At value 3, skipping gives 11, while taking gives 7 + 3 = 10. We skip that house and keep 11. At value 1, taking gives 11 + 1 = 12.

Pitfalls

• The best choice can switch from skip to take at any index.
• Do not interpret twoBack as the value at an earlier house; it is an optimized prefix total.
• Keep the example's values and update order aligned.

Recap

• The final rolling state is 12.
• One optimal set is houses with values 2, 9, and 1.
• Every transition remains legal because taking uses the state two positions back.

Learning goal: Recognize why plausible shortcuts fail and how the recurrence handles boundary cases.

Core idea The optimal solution depends on the values and on combinations of houses, not on a predetermined index pattern. A parity-based strategy can miss a very valuable house, while a locally largest choice can block an even better combination. Dynamic programming evaluates both legal possibilities at every position.

The parity mistake

Greedily taking all even-indexed or all odd-indexed houses is not generally correct. For [5, 1, 1, 5], taking even indices gives 6, while taking odd indices gives 2; the true optimum is 10 by taking the first and last houses. The best set can mix positions according to values.

Edge cases

• One house: return its value.
• Two houses: return the larger value.
• All zeros: return 0.
• Repeated values: still process each position normally.

Micro-example For [5, 1, 1, 5], the final 5 is compatible with the first 5 because two houses lie between them. The answer is 10, not the sum of one fixed parity class.

Pitfalls

• Do not always take the locally larger of two adjacent houses.
• Do not use nums[i - 1] when taking nums[i]; use the prior optimal total.
• Handle the empty prefix through initialization rather than invalid indexing.

Recap

• Values determine the choices; parity does not.
• Base initialization handles short arrays cleanly.
• Comparing both branches prevents greedy mistakes.

Learning goal: Justify the efficiency of the rolling dynamic programming solution.

Core idea Each house is processed exactly once, and each processing step performs a constant number of arithmetic operations and comparisons. Because only twoBack, oneBack, and a temporary current value are stored, the algorithm uses constant extra memory regardless of the number of houses.

Complexity

• Time: O(n), where n = nums.length.
• Extra space: O(1).

Final implementation pattern

def rob(nums):
    twoBack, oneBack = 0, 0
    for money in nums:
        current = max(oneBack, twoBack + money)
        twoBack, oneBack = oneBack, current
    return oneBack

Micro-example For [2, 7, 9, 3, 1], the rolling best totals finish at 12. The algorithm never needs to remember the full table to produce that result.

Pitfalls

• Space complexity counts extra storage, not the input array itself.
• Do not claim O(1) time: every house must be examined.
• Keep the state meaning consistent while shifting variables.

Recap

• Recurrence: max(skip, take + twoBack).
• Rolling state gives O(n) time and O(1) extra space.
• The no-adjacent constraint is enforced by using the state two positions back.