House Robber

The problem. Houses along a street hold nums[i] money each. Robbing two adjacent houses sets off the alarm. Return the most money you can rob without robbing two neighbours.

Example

nums = [1, 2, 3, 1]     ->  4    (rob houses 0 and 2)
nums = [2, 7, 9, 3, 1]  ->  12   (rob houses 0, 2 and 4)
nums = [2, 1, 1, 2]     ->  4    (rob houses 0 and 3)

The idea: rob it or skip it

Let best[i] be the most you can rob from houses 0..i. For house i there are two choices. Skip it: you keep best[i − 1]. Rob it: you get nums[i], but house i − 1 must be skipped, so add best[i − 2]. Take the better: best[i] = max(best[i − 1], best[i − 2] + nums[i]). Greedy rules like "take every other house" fail — [2, 1, 1, 2] needs houses 0 and 3.

1. Plain recursion

1function rob(nums) {2  const best = (i) => {                          // the most from houses 0..i3    if (i < 0) return 0;                         // no houses left4    return Math.max(best(i - 1), best(i - 2) + nums[i]);   // skip house i, or rob it5  };6  return best(nums.length - 1);7}

Time O(2ⁿ), space O(n).

2. A table

1function rob(nums) {2  const n = nums.length;3  const best = new Array(n).fill(0);             // best[i]: the most from houses 0..i4  for (let i = 0; i < n; i++) {5    const skip = i >= 1 ? best[i - 1] : 0;       // leave house i alone6    const take = nums[i] + (i >= 2 ? best[i - 2] : 0);   // rob it: house i - 1 must be skipped7    best[i] = Math.max(skip, take);8  }9  return best[n - 1];10}

Time O(n), space O(n).

3. Two variables

1function rob(nums) {2  let twoBack = 0, oneBack = 0;                  // best[i - 2], best[i - 1]3  for (const money of nums) {4    [twoBack, oneBack] = [oneBack, Math.max(oneBack, twoBack + money)];5  }6  return oneBack;7}

Time O(n), space O(1). Starting both variables at 0 handles the first two houses with no special cases.

Comparing the approaches

Edge cases to test

Variations