213. House Robber II

The houses now form a circle, so the first and last are adjacent and cannot both be robbed. Break the cycle by running the classic linear House-Robber DP twice — once skipping the first house, once skipping the last — and returning the max of the two results.

● MediumDPCircular ArrayTypeScript

PROBLEM What we're solving

Given nums where each element is the money in one house, rob the maximum total without robbing two adjacent houses. The twist: the houses are arranged in a circle, so house 0 and house n-1 are also adjacent. nums = [2,3,2] → 3 (rob only house 1; you cannot rob both house 0 and house 2 because they share the circular edge).

KEY IDEA Break the circle into two linear problems

Insight → in any valid robbery, house 0 and house n-1 are never both robbed. So the optimal answer is either the best robbery on nums[0..n-2] (last house excluded) or the best on nums[1..n-1] (first house excluded). Each sub-problem is a plain linear House Robber — a problem you already know.

RECIPE Two passes, take the max

0 · Edge case. If n === 1, return nums[0]— there's only one house to rob.
1 · Define a helper. robRange(start, end) runs the rolling-pair DP on the slice [start..end]: maintain rob1 (best two houses back) and rob2 (best up to previous house). At each step, newRob2 = max(rob2, rob1 + nums[i]).
2 · Pass A. Call robRange(0, n-2) — the last house is excluded so the first and last are no longer adjacent.
3 · Pass B. Call robRange(1, n-1) — the first house is excluded instead.
4 · Answer. Return max(passA, passB). The optimum must lie in one of these two non-circular sub-problems.

Classic confusion →beginners try to handle the circularity inside a single DP pass — adding extra states or a "can-touch-first" flag — and the recurrence gets tangled. The two-pass decomposition is cleaner precisely becauseit reduces a novel constraint to two copies of a known sub-problem. Run the same helper twice; don't modify it.

COST Complexity & alternatives

Brute force (all subsets)

O(2ⁿ)

Try every non-adjacent subset that respects the circle.

Two-pass rolling DP

O(n)

Two linear sweeps; O(1) space — just two variables each pass.

Space note

The rob1 / rob2 rolling pair needs only two variables per pass — no array required. The total extra space is O(1).

Pattern transfer →the "circular constraint → two linear sub-problems" trick reappears in House Robber III (DP on a tree), Maximum Sum Circular Subarray(Kadane's on the complement), and any problem where boundary adjacency creates a dependency that otherwise prevents a clean recurrence.

RUN IT Two linear passes on the circular array

nums =

step 0 / 8

STARTPass A (skip last): skip house 2 (dimmed). Initialize rob1=0, rob2=0.

1function rob(nums: number[]): number {
2  const n = nums.length;
3  if (n === 1) return nums[0];
4 
5  function robRange(start: number, end: number): number {
6▶    let rob1 = 0;
7▶    let rob2 = 0;
8    for (let i = start; i <= end; i++) {
9      const newRob2 = Math.max(rob2, rob1 + nums[i]);
10      rob1 = rob2;
11      rob2 = newRob2;
12    }
13    return rob2;
14  }
15 
16  // Houses form a circle: first and last are adjacent.
17  // Run linear DP twice: once excluding the last house,
18  // once excluding the first, then take the max.
19  return Math.max(robRange(0, n - 2), robRange(1, n - 1));
20}

203122

State

Pass A (skip last)

pass

—

rob1

rob2

—

newRob2

current houserobbedrolling max (rob2)excluded house (dimmed)

slowfast

TYPESCRIPT The solution, annotated

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

  function robRange(start: number, end: number): number {
    let rob1 = 0;
    let rob2 = 0;
    for (let i = start; i <= end; i++) {
      const newRob2 = Math.max(rob2, rob1 + nums[i]);
      rob1 = rob2;
      rob2 = newRob2;
    }
    return rob2;
  }

  // Houses form a circle: first and last are adjacent.
  // Run linear DP twice: once excluding the last house,
  // once excluding the first, then take the max.
  return Math.max(robRange(0, n - 2), robRange(1, n - 1));
}

Reading it block by block

Line 3 — single-house edge case. With only one house there is no adjacency constraint at all — the answer is simply nums[0]. Handling it early keeps the rest of the logic clean.

Lines 5–12 — the reusable helper. robRange(start, end) is exactly the linear House Robber: rob1 holds the best value achievable two or more positions back; rob2 holds the best up to the previous position. newRob2 = max(rob2, rob1 + nums[i]) asks: "rob this house (worth rob1 + nums[i]) or skip it (keep rob2)?" Then slide the window forward.

Line 17 — two-pass decomposition. Because house 0 and house n-1 are never both optimal, the true answer is the max of robRange(0, n-2) (exclude last) and robRange(1, n-1) (exclude first). The circular constraint is fully handled by the range bounds — no special casing inside the DP.

Complexity → O(n) time — two linear passes of length n-1. O(1) extra space — only rob1 and rob2 per pass, no auxiliary array.

INTERVIEWFollow-ups they'll ask

"Return the actual houses robbed, not just the amount." Track a parent[] array during each pass to reconstruct the chosen indices, then return the set from whichever pass won.
"What's the brute force?" Enumerate all 2ⁿ subsets, filter out those with adjacent or wrap-around pairs, and take the max sum. The DP replaces this with two O(n) passes.
"What if houses are on a line, not a circle?"That's plain House Robber I — run a single robRange(0, n-1). The circular version is strictly harder because it adds one extra adjacency constraint.
"What if k consecutive houses can't be robbed?" The rolling window grows to size k — maintain a sliding-window max with a deque instead of two variables.
"House Robber III — on a binary tree?" Recurse post-order; return a [withRoot, withoutRoot]pair from each subtree. The pattern is the same "take vs skip" DP, just on a tree shape.

OPTIMAL DP

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

  function robRange(start: number, end: number): number {
    let rob1 = 0;
    let rob2 = 0;
    for (let i = start; i <= end; i++) {
      const newRob2 = Math.max(rob2, rob1 + nums[i]);
      rob1 = rob2;
      rob2 = newRob2;
    }
    return rob2;
  }

  // Houses form a circle: first and last are adjacent.
  // Run linear DP twice: once excluding the last house,
  // once excluding the first, then take the max.
  return Math.max(robRange(0, n - 2), robRange(1, n - 1));
}

Complexity → O(n) time — two linear passes of length n-1. O(1) extra space — only rob1 and rob2 per pass, no auxiliary array.

ALT 1 Brute force — recurse on both circular cases

O(2ⁿ) time · O(n) space

Split the circle into two linear problems — houses 0..n-2 and 1..n-1— and solve each by the exponential rob-or-skip recursion, then take the larger.

approach-2.ts
function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0];

  function robLinear(start: number, end: number): number {
    function best(i: number): number {
      if (i > end) return 0;
      // rob house i and skip i+1, OR skip house i
      return Math.max(nums[i] + best(i + 2), best(i + 1));
    }
    return best(start);
  }

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

Note → Each linear pass branches at every house, so the whole thing is O(2ⁿ). Memoising best(i) within each pass makes it O(n); the rolling two-variable DP run twice is the O(1)-space optimum.

MNEMONIC The one-liner

"Circle means first and last can't coexist — so run the line twice: once without the last, once without the first."

TRIGGERS When you see _ → reach for _

houses in a circle, no two adjacent	two-pass linear House Robber DP
circular array, first↔last adjacency	decompose into two [0..n-2] / [1..n-1] sub-problems
rolling rob1/rob2 in a loop	linear DP, O(1) space
"what if it wraps around?"	exclude one endpoint per pass, take max

SKELETON The reusable shape

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

  function robRange(start: number, end: number): number {
    let rob1 = 0, rob2 = 0;
    for (let i = start; i <= end; i++) {
      const next = Math.max(rob2, rob1 + nums[i]);
      rob1 = rob2;
      rob2 = next;
    }
    return rob2;
  }

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

FLASHCARDS Tap to flip

Why can't you solve House Robber II with a single DP pass?

House 0 and house n-1are adjacent in the circle, creating a dependency between the first and last decisions that a left-to-right pass can't express cleanly.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the two-pass solution?

QUESTION 02

Why must we run two separate passes instead of one?

QUESTION 03

Trace nums = [2,3,2]. What does Pass A (robRange(0, 1)) return?

QUESTION 04

For nums = [1,2,3,1], the correct answer is:

QUESTION 05

What is the space complexity?

QUESTION 06

nums = [5]. The correct return value is:

QUESTION 07

A student writes robRange(0, n-1) for both passes (ignoring the circular constraint). What goes wrong?

QUESTION 08

#213 · House Robber IIThe houses form a circle, so the first and last are adjacent. Run the linear House-Robber DP twice — once excluding the first house, once excluding the last — and return the max of both passes.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Break the circle into two linear problems

RECIPE Two passes, take the max

COST Complexity & alternatives

Space note

RUN IT Two linear passes on the circular array

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL DP

ALT 1 Brute force — recurse on both circular cases

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _