House Robber II

Difficulty: Medium

Problem

Same burglar, new neighborhood: the houses now sit around a ring, so the first and last houses are next-door neighbors and hitting both sets off the alarm. The no-two-adjacent rule still applies. Find the largest total loot. The lesson: reduce a new problem to two runs of one you already solved.

Example

Input: nums = [4,1,2,9,3]
Output: 13
Explanation: Houses 0 and 4 are neighbors on the ring, so they cannot both be robbed. Taking houses 0 and 3 gives 4 + 9 = 13, and no other legal choice does better.

Brute-force approach

No new naive phase: the linear robber's full arc was last lesson. This lesson is about the reduction.

Optimal approach

Key insight: The first and last house can never both be robbed. That single fact dissolves the circle into two straight lines: both already solved by yesterday's algorithm.

Split on the one new conflict: solve the line without the last house and the line without the first house with the linear robber, then take the better result.

Steps

  1. Guard: one house → return its loot
  2. Case A: linear rob on nums[0..n−2] (last house excluded)
  3. Case B: linear rob on nums[1..n−1] (first house excluded)
  4. Answer: max(A, B)

Time complexity: O(n) · Space complexity: O(1) (plus the slices; index bounds avoid even those)

Pseudocode

function rob(nums):
    if length(nums) == 1:
        return ____
    
    function robLine(houses):
        prev2 = 0, prev1 = 0
        for x in houses:
            cur = max(prev1, prev2 + x)
            prev2 = prev1
            prev1 = cur
        return prev1
    
    caseA = robLine(nums without the ____ house)
    caseB = robLine(nums without the ____ house)
    return ____(caseA, caseB)

Hints

  • One house means no circle at all, return what?
  • Case A assumes the LAST house is skipped, which house leaves the array?
  • Case B assumes the FIRST is skipped
  • Every valid plan lives in one of the cases. How do we combine two maxima?

Complexity questions

Two linear passes instead of one, what's the complexity?

Still O(n): constants don't change the class. 2 × O(n) = O(n). Reductions that multiply work by a constant are effectively free.

What's the space complexity, and what small improvement exists?

O(1) for the rolling variables; passing index bounds instead of slicing avoids even the O(n) slice copies. The engine is O(1). nums[:-1] copies the array in Python, passing (lo, hi) bounds to rob_line makes the whole solution allocation-free.

The two cases overlap (plans skipping both ends appear in each). Why is that acceptable here?

We take a MAX: seeing a plan twice can't change the maximum. Counting problems would need disjoint cases. max(a, a) = a: duplicates are harmless to optimization. If this were 'COUNT the valid plans', overlapping cases would double-count and you'd need inclusion-exclusion or disjoint cases.

Where else does 'split on the wrap-around element' work?

Any circular-arrangement problem: circular seating, necklace partitions, circular subarray sums, fix the boundary element's fate, and the circle straightens. Circular constraints usually hinge on the seam. Case-splitting the seam's element (used / not used) converts the circle into one or two linear problems, a reusable design pattern.

Check your understanding of House Robber II

What exactly does the circle change?

ONE new constraint: house 0 and the last house are now adjacent, they can't both be robbed. Everything else is the linear problem you solved. The single new edge in the 'conflict graph' connects the two ends, and the whole solution flows from handling that one edge.

Why can't we just run the linear House Robber on the circle directly?

The linear dp never knows that its first and last choices conflict. It might rob both ends, which the circle forbids. On [2,3,2], linear DP happily answers 4 (rob both 2s), but they're neighbors on the circle. The linear recurrence has no way to remember a constraint between the two far ends.

The key observation that unlocks the reduction?

The first and last house can't BOTH be robbed, so every valid plan skips the first, or skips the last (or both). Any legal plan avoids at least one of the two ends. That splits ALL plans into two (overlapping-at-worst) cases. Each of which is a plain LINE.

So the algorithm is...?

Run linear rob() twice (once on nums without the last house, once without the first) and return the max. Case A (last house skipped) = linear robber on nums[0..n−2]. Case B (first skipped) = linear robber on nums[1..n−1]. Every valid circular plan lives in at least one case, so max(A, B) is the answer.

Which input needs special care?

A single house: both slices would be empty, so return nums[0] directly. With one house there IS no circle conflict, rob it. The slices nums[:-1] and nums[1:] would both be empty and wrongly answer 0. One guard line handles it.

Related problems

Keep practising