Free lesson · DSA Mastery - Interview Prep, End to End

House Robber II

Hard11 min readdsadynamic-programming

House Robber II

House Robber II adds one twist: the houses are arranged in a circle, so the first and last houses are now adjacent and cannot both be robbed. The elegant reduction is to run the linear House Robber twice - once on houses 0..n-2 (excluding the last house) and once on houses 1..n-1 (excluding the first house) - and return the larger, because any valid circular solution must omit at least one of house 0 or house n-1. It teaches the powerful technique of reducing a harder constrained problem to repeated applications of a simpler one: rather than inventing new circular-DP machinery, you recognize that the circular constraint splits into two linear cases you already know how to solve - a reduction pattern that recurs whenever a "wrap-around" or "either-or boundary" constraint can be handled by fixing one boundary choice and solving the rest with the base technique. We present the two-pass reduction (canonical).

The insight: the only new constraint versus linear House Robber is that house 0 and house n-1 are now adjacent. So in any valid robbery, you cannot rob both of them - at least one must be skipped. That observation splits the problem into two cases you already know how to solve: (case A) house 0 is not robbed, so consider only houses 1..n-1 as a line; (case B) house n-1 is not robbed, so consider only houses 0..n-2 as a line. Each case is plain linear House Robber. The optimal circular answer is the better of the two - because every valid solution falls into at least one case.

The Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input:  nums = [2,3,2]
Output: 3

Explanation: You cannot rob house 0 (money = 2) and house 2 (money = 2), because they are
adjacent in the circle. Robbing house 1 alone gives 3.

Example 2:

Input:  nums = [1,2,3,1]
Output: 4

Explanation: Rob house 0 (1) and house 2 (3). Total = 4. (House 0 and 3 are adjacent but not both robbed.)

Constraints:

1 <= nums.length <= 100; 0 <= nums[i] <= 1000.

Approaches Overview

#	Approach	Time	Space	Verdict
1	Two linear House Robber passes (reduction)	O(n)	O(1)	Canonical

Because house 0 and house n-1 are adjacent, no valid solution robs both. Split into two linear subproblems: rob within houses 0..n-2 (last excluded), and rob within houses 1..n-1 (first excluded). Each is solved by the linear House Robber DP (in O(n) time, O(1) space). The answer is the max of the two. A single house is a special case (just rob it). This reduces the circular constraint to two applications of the already-solved linear problem.

Approach: Two Linear Passes - Canonical

The Idea

The circular adjacency means house 0 and house n-1 cannot both be robbed. Therefore every valid solution either excludes house 0 or excludes house n-1 (or both). So compute two linear House Robber results - one over nums[0..n-2] (excluding the last), one over nums[1..n-1] (excluding the first) - and return the larger. Handle n == 1 directly (rob the only house). Each linear pass uses the O(1)-space rolling-variable House Robber.

Logic Flowchart

graph TD
    A["n == 1? return nums[0]"] --> B["caseA = robLinear(nums, 0, n-2)  (exclude last)"]
    B --> C["caseB = robLinear(nums, 1, n-1)  (exclude first)"]
    C --> D["return max(caseA, caseB)"]
    D --> E["every valid circular solution omits house 0 or house n-1"]

    style A fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows House Robber Two by reduction: a single house is robbed directly, otherwise solve two linear cases - excluding the last house and excluding the first house - and return the larger.

Code

public static int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];                        // single house: just rob it
    // Case A: exclude the last house (rob within indices 0..n-2).
    // Case B: exclude the first house (rob within indices 1..n-1).
    return Math.max(robLinear(nums, 0, n - 2),
                    robLinear(nums, 1, n - 1));
}

// Linear House Robber over the inclusive index range [lo, hi].
private static int robLinear(int[] nums, int lo, int hi) {
    int prev2 = 0, prev1 = 0;                          // O(1)-space rolling House Robber
    for (int i = lo; i <= hi; i++) {
        int cur = Math.max(prev1, prev2 + nums[i]);    // skip house i, or rob it
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

// Usage:
// rob([2,3,2]) -> 3
// rob([1,2,3,1]) -> 4

This Java code solves circular House Robber by reduction: it runs the linear House Robber twice, once excluding the last house and once excluding the first, and returns the larger result.

Step-by-Step Walkthrough

Tracing rob([2,3,2]):

graph LR
    F0["n=3. Case A: houses [0..1] = {2,3}"]
    F1["robLinear({2,3}) = max(2,3) = 3"]
    F2["Case B: houses [1..2] = {3,2}; robLinear = max(3,2) = 3"]
    F3["return max(3, 3) = 3"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough robs a circle of three houses: excluding the last gives three, excluding the first gives three, so the answer is three - you cannot rob both end houses.

Result: 3.

Complexity

Time: O(n) - two linear passes, each O(n). Space: O(1) - the rolling-variable House Robber.

Complexity Comparison

Approach	Time	Space	Key Idea
Two linear passes (reduction)	O(n)	O(1)	Circular constraint → exclude house 0 or house n-1; two linear cases

The reduction is the canonical solution. Rather than inventing circular-DP machinery, recognize that the only new constraint (house 0 and house n-1 are adjacent) forces every valid solution to omit at least one of them - splitting the problem into two linear House Robber subproblems you already know how to solve. The answer is the better of the two passes. This "fix a boundary choice, reduce to the base case" technique is broadly powerful.

Variations & Follow-ups

Why does excluding house 0 or house n-1 cover all valid solutions?

The correctness of the two-pass reduction rests on a clean logical argument. The only difference between circular House Robber and linear House Robber is the new adjacency between house 0 and house n-1. In the linear version, those two ends are not adjacent, so a linear solution might rob both. In the circular version, robbing both is forbidden. So every valid circular solution must satisfy: not both house 0 and house n-1 are robbed - equivalently, house 0 is excluded, OR house n-1 is excluded (or both). This is a logical partition: any valid solution falls into "house 0 not robbed" (case A) or "house n-1 not robbed" (case B), with overlap (solutions robbing neither) allowed. Case A (house 0 excluded): the remaining houses 1..n-1 form a line (house n-1's only circular neighbor, house 0, is gone, so no wrap-around constraint remains) - plain linear House Robber on nums[1..n-1]. Case B (house n-1 excluded): houses 0..n-2 form a line - linear House Robber on nums[0..n-2]. Taking the max of the two cases finds the best valid solution, because every valid solution is captured by at least one case, and neither case ever produces an invalid solution (each excludes one end, so the forbidden "both ends robbed" can never occur). The overlap (solutions robbing neither end) is harmless - it is just counted in both cases, and the max is unaffected. So the two cases are exhaustive (cover all valid solutions) and sound (never produce invalid ones), which is exactly what a correct reduction requires. This exhaustive-and-sound case split is the heart of the technique: identify a binary choice that the hard constraint forces, and solve each branch with the simpler method.

Why is reducing to the base problem better than inventing circular DP?

You could try to design a bespoke "circular DP" that directly handles the wrap-around constraint within a single pass - tracking, say, whether house 0 was robbed as part of the state. That works but is more complex and error-prone: you would augment the state with a boolean ("did I rob house 0?"), double the state space, and carefully handle the wrap-around in the final step. The reduction sidesteps all of that. By recognizing that the circular constraint factors into a binary boundary choice (exclude house 0 or exclude house n-1), you reduce the new problem to two instances of a problem you have already solved correctly. This is almost always preferable when available: reuse beats reinvention. You inherit the correctness, simplicity, and efficiency of the linear House Robber, paying only a factor-of-2 in time (two passes) and nothing in conceptual complexity. The general principle: when a problem is a base problem plus a constraint on a boundary or a special element, try fixing the choice at that boundary/element and solving the rest with the base technique, then take the best over the fixed choices. This "case-split on a boundary, reduce to the base case" pattern recurs widely. It is the same spirit as: solving a problem "with at most one of X" by trying "without X" and "forcing X" (seen in the MST critical-edges problem from the Graphs module); or handling a circular array by considering it as two linear arrays. The skill is recognizing that the added constraint creates a small number of cases, each reducible to the simpler problem. Reducing to a known solution is not a fallback - it is often the cleanest and most reliable approach, and interviewers value the insight of "I can reduce this circular problem to two linear ones I already know."

How does this case-split / boundary-fixing technique generalize?

The "fix a boundary choice, reduce to the base case" technique appears throughout DP and algorithms whenever a constraint couples special elements. Circular arrays are the prototypical trigger: any problem on a circular array where the wrap-around creates an adjacency/coupling can often be split by fixing whether a particular boundary element is used. "At most one" / "exactly one" constraints: to solve "best solution using at most one special move," try "without the move" and "forcing the move at each position," taking the best (the MST critical-edge analysis did this). Either-or constraints: if a constraint says "not both A and B," split into "without A" and "without B" and take the best - exactly House Robber II's split. Fixing the first/last decision: many DP problems simplify if you fix the first or last choice and solve the remainder as a base subproblem. The unifying idea: a hard constraint often factors into a small set of mutually-exhaustive cases, each of which removes the constraint and reduces to a simpler (often already-solved) problem; solve each case independently and combine (usually by max/min/sum). The cost is a small multiplicative factor (the number of cases); the benefit is reusing simpler, trusted machinery instead of building complex augmented-state DP. Recognizing when a constraint factors this way - typically when it couples a bounded number of special elements or boundaries - is the skill. House Robber II is the cleanest teaching instance: one coupling (house 0 and house n-1), two cases (exclude one or the other), each a linear House Robber. Internalize this, and circular/boundary-constrained problems become "case-split, then apply the base solution," rather than daunting new DPs to design from scratch.

How does House Robber II complete the House Robber progression?

House Robber II is the second rung of a three-rung progression that demonstrates how a single core pattern scales to richer structures. House Robber (linear): the base - include/exclude each house with an adjacency constraint, on a line. House Robber II (circular): the same linear DP, applied twice via a boundary case-split to handle the circular adjacency. House Robber III (in the Tree DP sub-group): the same include/exclude-with-adjacency logic, but on a binary tree, where "adjacent" means parent-child, and the transition combines a node's children's results (each child contributing a "robbed" and "not robbed" value). The progression teaches that the core decision - at each house/node, rob it (gaining its value but forbidding its neighbors) or skip it - stays constant, while the structure on which it operates grows: line → circle → tree. The circle is handled by reduction (two linear passes), the tree by lifting the recurrence onto the tree (post-order DP combining children). Seeing this progression builds the meta-skill of recognizing a familiar pattern under new structure and choosing the right adaptation: sometimes you reduce to the base case (the circle), sometimes you generalize the recurrence to the new structure (the tree). House Robber II specifically teaches the reduction response - when added structure (the wrap-around) can be eliminated by a boundary case-split, do that rather than redesigning the DP. This is the more elegant of the two responses when it applies, and recognizing its applicability (a bounded coupling that factors into cases) is the lesson. Together, the three House Robber variants are a masterclass in pattern transfer: same decision engine, three structures, two adaptation strategies (reduce vs. generalize).

What about edge cases?

Single house (n == 1): No circular adjacency to worry about; just rob it (nums[0]). Handle before the two passes (the ranges 0..n-2 and 1..n-1 are empty or degenerate otherwise).
Two houses (n == 2): They are adjacent in the circle; rob the richer. Case A robs nums[0], case B robs nums[1]; max gives the right answer.
Three houses (Example 1): Cannot rob two ends; the DP picks the best single or valid pair.
All equal values: The circular constraint still forbids both ends; the DP finds a valid maximum.
n even vs. odd: No special handling needed; the two-pass reduction works regardless.

Common Interview Pitfalls

Applying linear House Robber directly. It would allow robbing both ends, violating the circular adjacency; you must split into the two cases.
Forgetting the single-house case. With n == 1, the ranges 0..n-2 and 1..n-1 are empty; handle n == 1 separately.
Excluding the wrong houses. Case A excludes the last house (range 0..n-2); case B excludes the first (range 1..n-1). Mixing these up breaks the reduction.
Over-engineering with augmented-state DP. The two-pass reduction is simpler and less error-prone than tracking "did I rob house 0?" in the state.

Why This Topic Matters

House Robber II teaches reducing a constrained problem to repeated applications of a simpler one: the circular adjacency forbids robbing both house 0 and house n-1, so every valid solution excludes at least one of them - splitting into two linear House Robber passes (exclude the last, exclude the first) whose max is the answer. This "fix a boundary choice, reduce to the base case" technique - recognizing that an added constraint factors into a bounded set of exhaustive, sound cases each reducible to a known solution - is broadly powerful for circular arrays, "at most/exactly one" constraints, and either-or couplings. Reuse beats reinventing a complex augmented-state DP.

The next topic, Maximum Length of Pair Chain, shifts the 1-D DP flavor toward subsequence / chaining problems: given pairs [a, b], a pair [c, d] can follow [a, b] in a chain if b < c, and you want the longest chain you can form. After sorting the pairs by their second element, this becomes either a greedy selection (always take the pair that ends earliest, like interval scheduling) or a DP closely related to Longest Increasing Subsequence - dp[i] = the longest chain ending with pair i, built by extending any earlier compatible pair. It bridges 1-D DP toward the Longest Increasing Subsequence sub-group, introducing the idea of sorting to impose an order so that a chaining/subsequence DP (or a greedy) becomes possible - a preprocessing step that unlocks many sequence-DP problems and previews the LIS pattern to come.

Back to DSA Mastery - Interview Prep, End to End