Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumone-dimensional-dp

House Robber II

Problem (restated)

Houses in a circle (first adjacent to last). Cannot rob adjacent houses. Maximize money.

Intuition

Cannot take both ends. Answer = max(rob [0..n-2], rob [1..n-1]) with classic linear House Robber DP.

Approaches

Two linear robber ranges

Unverified

Time O(n)Space O(1)

Idea. Handle n=1 specially. Reuse O(1) rolling DP on each open range.

Walkthrough. [2,3,2] → 3; [1,2,3,1] → 4.

Trade-offs. Circle breaks pure linear recurrence; case split fixes it.

Solution

export function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0]!;
  const linear = (l: number, r: number): number => {
    let prev2 = 0, prev1 = 0;
    for (let i = l; i <= r; i++) {
      const cur = Math.max(prev1, prev2 + nums[i]!);
      prev2 = prev1;
      prev1 = cur;
    }
    return prev1;
  };
  return Math.max(linear(0, n - 2), linear(1, n - 1));
}

export function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0]!;
  const linear = (l: number, r: number): number => {
    let prev2 = 0, prev1 = 0;
    for (let i = l; i <= r; i++) {
      const cur = Math.max(prev1, prev2 + nums[i]!);
      prev2 = prev1;
      prev1 = cur;
    }
    return prev1;
  };
  return Math.max(linear(0, n - 2), linear(1, n - 1));
}

Template connection

1D House Robber with circular constraint.

Reflection

The first house and the last house are neighbors. Run the linear robbery twice: drop the first house, then drop the last. Keep the larger result.
n = 1 is that house. n = 2 is the larger of the two. Taking both breaks the circle.
The range helper is the linear robber. An empty range is 0.