House Robber

Approach Summary

At each house: either rob it (prev_prev + current) or skip it (prev). Track two previous values.

Full Solution & Approach

A classic DP where the state is the best loot up to house i. At each house you either skip it (best up to i - 1) or rob it (its value plus the best up to i - 2, since you cannot rob the adjacent house). So dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The recurrence only needs the previous two values, so collapse the array into two rolling variables: prev = dp[i-2] and curr = dp[i-1]. For each house, next = max(curr, prev + n), then shift prev = curr and curr = next. Initialize both to 0 to model the empty prefixes. This is the same skeleton as Climbing Stairs but with a max() combining two choices instead of a sum — the take-or-skip pattern reappears in many 1D DP problems.

One pass over n houses with constant work — O(n) time. Two rolling variables — O(1) extra space.

Solution Code

Solution

def rob(nums: list[int]) -> int:
    prev = curr = 0
    for n in nums:
        prev, curr = curr, max(curr, prev + n)
    return curr

function rob(nums) {
  let prev = 0, curr = 0;
  for (const n of nums) {
    [prev, curr] = [curr, Math.max(curr, prev + n)];
  }
  return curr;
}

public int rob(int[] nums) {
    int prev = 0, curr = 0;
    for (int n : nums) {
        int temp = curr;
        curr = Math.max(curr, prev + n);
        prev = temp;
    }
    return curr;
}

int rob(const vector<int>& nums) {
    int prev = 0, curr = 0;
    for (int n : nums) {
        int temp = curr;
        curr = max(curr, prev + n);
        prev = temp;
    }
    return curr;
}

Edge Cases to Watch

Empty array — return 0
Single house — its value
Two houses — the larger of the two
All houses equal — robbing every other house

How to Recognize This Pattern

Cannot take adjacent elements
Max sum with gap-1 constraint

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)