House RobberMedium

Given an array of non-negative amounts of money in houses arranged in a line, find the max total you can rob without robbing two adjacent houses.

Examples

Input: nums = [1,2,3,1] → Output: 4 — rob house 0 (1) and house 2 (3)

Approach

Brute-force recursion branches at every house into 'rob it' (and skip the next one) versus 'skip it', recomputing the same sub-decisions repeatedly. Bottom-up DP collapses this: at each house, the best possible total is either the best total without this house, or this house's value plus the best total from two houses back. Two rolling variables carry that forward without needing a full array.

Complexity — best & worst case

Brute force — time O(2ⁿ)

Optimal (bottom-up) — time O(n), best and worst case are the same — always processes every house

Optimal (bottom-up) — space O(1) — two rolling variables

Code

// Given an array of non-negative amounts of money in houses arranged
// in a line, find the max total you can rob WITHOUT robbing two
// adjacent houses (that trips the alarm).

// --- Brute force: at each house, branch into "rob it" vs "skip it" ---
function robBrute(nums, i = 0) {
  if (i >= nums.length) return 0;
  const robThis = nums[i] + robBrute(nums, i + 2); // skip the next house
  const skipThis = robBrute(nums, i + 1);
  return Math.max(robThis, skipThis);
}

// --- Optimal: bottom-up DP with two rolling variables, O(1) space ---
// At each house, the best you can do is either:
//   - skip it, keeping whatever the best was up to the previous house
//   - rob it, adding its value to the best up to two houses back
function rob(nums) {
  let prev2 = 0; // best total using houses[0..i-2]
  let prev1 = 0; // best total using houses[0..i-1]

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

// --- Example Usage ---
console.log(rob([1, 2, 3, 1]));      // 4, rob house 0 (1) and house 2 (3)
console.log(robBrute([1, 2, 3, 1])); // 4, same answer
console.log(rob([2, 7, 9, 3, 1]));   // 12, rob houses 0, 2, 4 (2+9+1)