House Robber II

Examples

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

Robbing houses 0 and 2 isn't allowed since they're adjacent in the circle, so the best is just house 1 (3).

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

Rob houses 0 and 2: 1 + 3 = 4. House 3 can't join house 0 since they're now neighbors.

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

All three houses touch each other in a circle of 3, so only one house can be robbed.

Constraints

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 1000

Approach

The circular wrap-around only matters because of one pair: house 0 and the last house. Any robbery plan either skips house 0 entirely, or skips the last house entirely — it's never allowed to include both.

So break the circle into two straight-line versions of the same problem: one that considers every house except the last, and one that considers every house except the first. Solve each with the ordinary House Robber approach, and take whichever total is bigger. The one edge case to handle separately is a single house, since a street of one house has no neighbors to conflict with.

Solutions

Brute Force — Two Linear Recursions

Recursively solve plain (non-circular) House Robber on the range that excludes the last house, and again on the range that excludes the first house, then take the max of the two.

function rob(nums) {
  const n = nums.length;
  if (n === 1) return nums[0];

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

  const excludeLast = bestInRange(0, n - 2);
  const excludeFirst = bestInRange(1, n - 1);
  return Math.max(excludeLast, excludeFirst);
}

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

Optimal — Bottom-Up Twice

Run the O(n) two-variable House Robber sweep on the slice that drops the last house, then again on the slice that drops the first house, and return the larger result.

function rob(nums) {
  const n = nums.length;
  if (n === 1) return nums[0];

  function robLine(houses) {
    let prev2 = 0;
    let prev1 = 0;
    for (const money of houses) {
      const current = Math.max(prev1, prev2 + money);
      prev2 = prev1;
      prev1 = current;
    }
    return prev1;
  }

  const excludeLast = robLine(nums.slice(0, n - 1));
  const excludeFirst = robLine(nums.slice(1));
  return Math.max(excludeLast, excludeFirst);
}

Time: O(n) · Space: O(n) — for the two slices