House Robber

Difficulty: Medium

You're a burglar planning to rob houses along a street. Each house holds some amount of cash, given as an array nums. Every house is wired to a security system connected to its immediate neighbors — if you rob two houses that are next to each other, the alarm goes off. Figure out the maximum amount of money you can steal without ever robbing two adjacent houses.

Examples

Input: nums = [1, 2, 3, 1]
Output: 4

Rob house 0 (1) and house 2 (3): 1 + 3 = 4.

Input: nums = [2, 7, 9, 3, 1]
Output: 12

Rob houses 0, 2, and 4: 2 + 9 + 1 = 12.

Constraints

  • 1 <= nums.length <= 100

  • 0 <= nums[i] <= 400

Approach

At each house, you make a binary decision: rob it, or don't. If you skip house i, your best total is whatever you could already get from the first i houses. If you rob house i, you collect nums[i] but you must not have robbed house i-1, so you add it to the best total from the first i-1 houses. Since you don't know in advance which choice is better, take whichever of the two gives more money.

That gives a clean recurrence: the best total through house i is max(best through i-1, best through i-2 + nums[i]). Just like Climbing Stairs, each step only needs the previous two results, so you can sweep through the array once, carrying only two running values forward.

Solutions

Brute Force — Plain Recursion

At each house, recursively try both 'skip it' and 'rob it', and take the better outcome. Correct, but explores overlapping subproblems exponentially many times.

function rob(nums) {
  function best(i) {
    if (i < 0) return 0;
    const skip = best(i - 1);
    const take = best(i - 2) + nums[i];
    return Math.max(skip, take);
  }

  return best(nums.length - 1);
}

Time: O(2^n) · Space: O(n) — recursion depth

Optimal — Bottom-Up with Two Variables

Sweep left to right, tracking the best total using only the last two houses' results — no need to store the whole array of results.

function rob(nums) {
  let prev2 = 0; // best total through two houses ago
  let prev1 = 0; // best total through the previous house

  for (const money of nums) {
    const current = Math.max(prev1, prev2 + money);
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

Time: O(n) · Space: O(1)