House Robber

Problem in plain words

Houses stand in a row and each holds some money. You can rob any set of houses as long as no two chosen houses are next to each other (adjacent robberies trigger an alarm). Return the largest total you can collect.

For example, with [5, 1, 1, 5] the best plan robs the first and last houses for 10; robbing the two middle ones is not allowed.

Intuition

At each house you face one decision. Skip it, and your best total is whatever you had after the previous house. Rob it, and you must have skipped the previous house, so you add its money to the best total from two houses back. Taking the larger option at every house gives the optimum, because the best answer for a prefix never depends on anything further right. Like the bottom-up Fibonacci DP lesson, only two earlier values are ever needed.

Approach

1. State: best[i] is the most money from houses 0..i.
2. Recurrence: best[i] = max(best[i - 1], best[i - 2] + nums[i]).
3. Base cases: treat best[-2] = best[-1] = 0, so the first house gives best[0] = nums[0].
4. Order: left to right, storing the previous two values as prev2 and prev1. The answer is prev1 at the end.

Dry run

Input: nums = [3, 1, 4, 9, 2].

The answer is 12, from robbing houses 0 and 3.

Java solution

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;   // best up to i-2, best up to i-1
        for (int money : nums) {
            int current = Math.max(prev1, prev2 + money);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

Python solution

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2, prev1 = 0, 0   # best up to i-2, best up to i-1
        for money in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + money)
        return prev1

Complexity

Edge cases and common mistakes

• One house: the loop runs once and returns nums[0].
• Robbing every other house greedily: picking all even or all odd indices fails on inputs like [2, 1, 1, 9], where the best is 2 + 9 = 11 (indices 0 and 3).
• Zero-money houses: values can be 0; the max handles them without special cases.
• Variable update order: compute the new value before shifting prev2 = prev1, or you lose the value from two houses back.