House Robber

Rob houses in a row for the most money without robbing two neighbours. For each house: either skip it (keep the best so far) or rob it (its money plus the best up to two houses back). Keep two rolling values.

Traced input: nums = [2, 7, 9, 3, 1] → 12. Original problem: neetcode.io/problems/house-robber

Complexity

Two variables: best including up to i−1 and up to i−2.

Key idea

• best(i) = max(best(i−1), best(i−2) + nums[i]).
• prev1 is the best up to the previous house, prev2 up to the one before.
• Skipping two houses in a row is never forced; the recurrence handles it.

Common mistakes

• Greedy (take every other house) fails on [2, 1, 1, 2].
• Initialising with nums[0] and nums[1] separately leads to edge-case bugs; zeros work.

Solution

int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;
    for (int i = 0; i < nums.length; i++) {
        int cur = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

def rob(nums: List[int]) -> int:
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

int rob(vector<int>& nums) {
    int prev2 = 0, prev1 = 0;
    for (int x : nums) {
        int cur = max(prev1, prev2 + x);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Edge cases

Each one has its own trace in the interactive view.