House Robber II

The problem

Same as House Robber, but houses form a circle: first and last are adjacent. Can’t rob both.

[2,3,2] → 3
[1,2,3,1] → 4  // 1 + 3 or 2+1 → 4
[1,2,3] → 3

Key reduction

In an optimal solution, either:

• We skip house 0 → solve linear on nums[1..n-1]
• We skip house n-1 → solve linear on nums[0..n-2]

Take the max. (Both might skip ends; still covered.)

Brute

Same exponential recursion with mask of used ends — unnecessary once you see the split.

Optimal

function robLinear(nums: number[], lo: number, hi: number): number {
  // max rob on nums[lo..hi] inclusive
  let prev2 = 0;
  let prev1 = 0;
  for (let i = lo; i <= hi; i++) {
    const cur = Math.max(prev1, prev2 + nums[i]);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 0) return 0;
  if (n === 1) return nums[0];
  if (n === 2) return Math.max(nums[0], nums[1]);

  return Math.max(
    robLinear(nums, 0, n - 2),
    robLinear(nums, 1, n - 1)
  );
}

Time	O(n)
Space	O(1)

Why n=1 special?

Both ranges would be empty or invalid if you naïvely do 0..n-2 and 1..n-1 without a base — single house should return that house.

Edge cases

• 1 house, 2 houses
• All equal values
• Increasing array

Common mistakes

• Running one linear pass on the full circular array
• Double-counting by adding house 0 and n-1 checks incorrectly
• Forgetting n ≤ 2 bases

Interview delivery

1. Circle = first/last adjacent.
2. Two linear subproblems.
3. Reuse House Robber I helper.
4. Edge n=1.
5. O(n).

Mental model

The circle only adds one constraint: house 0 and house n−1 conflict. Case-split on which end is excluded, solve two linear robber problems, take max. Don’t invent a fancy circular DP unless you enjoy pain.

Why both ranges

Optima that rob neither end are included in both linear solutions, so taking max doesn’t miss them. Optima that rob the first can’t rob the last and vice versa.

Out-loud answer

“Circular adjacent ends. Answer is max of linear rob on [0..n-2] and [1..n-1], with base cases for n≤2. Reuse House Robber I helper. O(n)/O(1).”

Full walk [1,2,3,1]

Linear on [1,2,3] (skip last): rob yields max(1+3, 2)=4.
Linear on [2,3,1] (skip first): max(2+1, 3)=3.
Answer max(4,3)=4.

Complexity table

Approach	Time	Space	Notes
Two linear robs	O(n)	O(1)	preferred
One DP with states about ends	O(n)	O(1)	easy to mess up
Exponential	O(2^n)	O(n)	warm-up only

Interview delivery

1. Circle constraint.
2. Case split ends.
3. Code linear helper once.
4. n=1 base.
5. O(n)/O(1).

Related

• House Robber
• Climbing Stairs
• Jump Game
• Binary Tree Max Path Sum
• JavaScript Interview Guide

Further reading

• LeetCode 213 — House Robber II
• LeetCode 198 — House Robber