House Robber II

MediumDynamic ProgrammingArrayDynamic Programming

Problem

This is the House Robber setup with one twist: the houses are arranged in a circle, so the first and last houses now count as neighbors too, in addition to every other adjacent pair. Find the maximum total you can collect without robbing two adjacent houses anywhere around the circle.

Example. For houses holding [2, 3, 2], robbing both the first and last house is not allowed since they are adjacent in the circle, so the best plan is just the middle house, giving 3.

Key idea

The plain House Robber recurrence assumes a straight line and breaks at the one seam where the last house wraps around to touch the first. Rather than inventing a new recurrence for that wraparound, notice that any valid plan can include the first house or the last house, but never both, since they are adjacent. So the answer is fully captured by two straight-line subproblems: the best plan over all houses except the last one, and the best plan over all houses except the first one. Neither subproblem has a wraparound left, so the ordinary linear House Robber DP solves each directly, and the circular answer is just the larger of the two results.

Solution

function rob(nums: number[]): number {
  if (nums.length === 1) {
    return nums[0]; // no wraparound possible with a single house
  }

  // break the circle two ways: drop the last house, or drop the first
  return Math.max(robLinear(nums.slice(0, nums.length - 1)), robLinear(nums.slice(1)));
}

function robLinear(houses: number[]): number {
  let prevBest = 0;
  let prevPrevBest = 0;

  for (const money of houses) {
    const robCurrent = prevPrevBest + money;
    const best = Math.max(prevBest, robCurrent); // skip or rob this house, take the larger
    prevPrevBest = prevBest;
    prevBest = best;
  }

  return prevBest;
}

Complexity

  • Time: O(n). Two linear passes, one over each trimmed subarray.
  • Space: O(1). Each linear pass only needs its previous two running totals.

Watch out for

  • A circle of one house is a special case: trimming either end leaves an empty array, so return its value directly.
  • Both trimmed subarrays still forbid adjacent picks internally; the circular constraint is handled only by the trimming itself.
  • Capping the DP at the ends instead of running two full passes misses plans that use the last house while avoiding the first.

Pattern

This is a case-split reduction: an awkward circular dependency is removed by considering the two ways to break the cycle and solving each straight-line problem with an already-known DP, then combining the results. The same "cut the cycle two ways" idea helps whenever a single wraparound edge is the only obstacle to reusing a linear algorithm.

Related questions