4.23.4 — House Robber II

LeetCode 213 · Medium

The problem

The same as 4.23.3, except the houses are arranged in a circle — so the first and last are adjacent and cannot both be robbed.

[2,3,2]      →  3     (cannot take both 2s; they are neighbours)
[1,2,3,1]    →  4     (houses 0 and 2)

The pattern

The circle adds one constraint: not both the first and the last.

Trying to handle a circle directly inside the DP gets messy — you would have to remember, at the last house, whether you robbed the first one, which means carrying an extra piece of state through the whole loop.

There is a much simpler move:

Split the problem so the constraint disappears.

Since the first and last cannot both be robbed, every valid answer falls into one of two cases:

1. The first house is not robbed — so the choice is over houses 1 … n−1, which is a plain line.
2. The last house is not robbed — so the choice is over houses 0 … n−2, also a plain line.

Every possible answer is covered. Case 1 allows the last house, case 2 allows the first, and neither allows both. Run the linear solver on each range and take the larger.

Note the cases overlap — an answer robbing neither the first nor the last appears in both. That is harmless, because you are taking a maximum, not a sum. If you were counting, overlapping cases would double-count and the split would be wrong. Knowing when overlap matters is the real lesson here.

The solution

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]                   # a single house has no neighbour

        def rob_line(houses) -> int:
            two, one = 0, 0
            for n in houses:
                two, one = one, max(n + two, one)
            return one

        return max(rob_line(nums[1:]),        # skip the first
                   rob_line(nums[:-1]))       # skip the last

TypeScript

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

  const robLine = (houses: number[]): number => {
    let two = 0, one = 0;
    for (const n of houses) [two, one] = [one, Math.max(n + two, one)];
    return one;
  };

  return Math.max(robLine(nums.slice(1)), robLine(nums.slice(0, -1)));
}

The single-house guard is required. With n = 1, nums[1:] is empty and nums[:-1] is empty, so both calls return 0 and the answer would be 0 instead of nums[0].

Two houses needs no special case. nums[1:] is [nums[1]] and nums[:-1] is [nums[0]], so the maximum is the larger of the two. Correct — they are adjacent, so you take one.

The helper is 4.23.3 unchanged. That is the point: you did not modify the algorithm, you removed the constraint by changing the input.

If you want to avoid the slices allocating copies, pass index ranges instead:

def rob_range(lo, hi):
    two, one = 0, 0
    for i in range(lo, hi + 1):
        two, one = one, max(nums[i] + two, one)
    return one

return max(rob_range(1, len(nums) - 1), rob_range(0, len(nums) - 2))

O(1) extra space rather than O(n). Worth mentioning if asked about memory.

Complexity

O(n) time — two linear passes. O(1) space with the index version, O(n) with the slices.

The technique, stated generally

When one awkward constraint links the two ends of a problem, split into cases that each remove it, solve each with the simpler algorithm, and combine.

This shows up repeatedly:

• Circular arrays — Maximum Sum Circular Subarray splits into "the answer does not wrap" (plain Kadane) and "it wraps" (total minus the minimum subarray).
• Best Time to Buy and Sell Stock with a cooldown — split by which state you are in.
• Any "exactly one of these two things" constraint — try it both ways.

The condition for the split to be valid: the cases must cover every possibility. They may overlap when you are taking a maximum or minimum; they must be disjoint when you are counting.

Where this goes next

• House Robber III — the same choice on a tree. Each node returns a pair: the best if this node is taken, and the best if it is not. The parent picks accordingly. It is the 4.14.3 "return two things" structure applied to DP.
• Maximum Sum Circular Subarray — the same circular split with Kadane's algorithm.
• Delete and Earn — bucket by value, then this exact recurrence.

What the interviewer will push on

"How do you handle the circle?" Two runs, each excluding one end. Say why every answer is covered.

"Do the two cases overlap, and does that matter?" They do, and it does not, because you take a maximum. It would matter if you were counting.

"Why the single-house special case?" Both ranges become empty.

"Could you do it in one pass?" Yes, by carrying "did I rob the first house" through the loop — but it doubles the state and is harder to get right. Two passes is the better engineering answer, and saying that is the point.

One thing to volunteer: name the technique. "Rather than complicate the DP, I remove the constraint by splitting into two cases and reusing the linear solver." Reusing a solved problem unchanged is a stronger answer than writing a cleverer one.

Next: 4.23.5 Longest Palindromic Substring — where the best solution is not the DP.