Loading…

mediumDynamic ProgrammingLC #213Sometimes asked

House Robber II

Q: How do you solve House Robber II using the Brute Force — Recursion With Endpoint Cases approach?

When to use it: Say this first to expose how the circle splits into two open-ended cases, then flag the exponential recursion before optimizing. The circular constraint sounds scary, but it collapses to a single observation: in any valid plan, **house 0 and house n-1 are never both robbed**. So enumerate the two ways to honor that: either we leave house 0 out (and the remaining houses `1 .. n-1` form a straight line) or we leave house n-1 out (houses `0 .. n-2` form a straight line). The optimal circular answer is the better of these two linear answers. **The mental shift: break the cycle by fixing an endpoint.** A ring is hard because the two ends wrap into each other. The instant you *force* one end to be excluded, the wrap-around disappears and you're left with the plain line problem you already know how to solve. Two cases cover every possibility because at least one end must be missing. **Why two cases, not three.** You might worry about the plan that robs neither end — but that plan is already a sub-case of *both* ranges, so it's covered. There's no scenario that escapes both `[0 .. n-2]` and `[1 .. n-1]`. **Why we don't ship this.** Each linear recursion overlaps subproblems exponentially, exactly like House Robber I. Name the reduction, then cache it. Time complexity: O(2ⁿ). Space complexity: O(n).

Q: How do you solve House Robber II using the Top-Down Memoization approach?

When to use it: The fix once the overlap is named — 'cache each suffix within a range so each linear pass is O(n)'. Keep the two-range reduction, but memoize each linear pass so the exponential recursion becomes linear. For a given range, `solve(i)` caches the best loot achievable from house `i` to the range's end; the second time that suffix is needed it's a free read. **The mental shift: memoize the inner problem, not the outer split.** The circular reduction is just two independent linear problems. We don't memoize across the split — each pass gets its own cache because index `i` means different things relative to each range. Inside a pass, the optimization is identical to House Robber I: cache `solve(i)` once. **Why a fresh cache per range.** If both passes shared one memo, an answer computed for range `[0 .. n-2]` could be wrongly reused for range `[1 .. n-1]`, where the boundaries differ. Resetting the cache (or keying it by range) keeps the two passes correct and independent. **Why the sentinel is -1.** Money can be 0, so 0 is a valid cached answer. Use -1 to mark 'not computed' so a genuine zero suffix isn't mistaken for a cache miss. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve House Robber II using the Bottom-Up — Two Linear Passes, Two Variables Each (Optimal) approach?

When to use it: The answer they want. Frame it as 'reuse the O(1) linear House Robber on two ranges and take the max'. Combine the reduction with the constant-space linear solver. Write a helper `robLinear(lo, hi)` that runs the familiar two-variable House Robber over an index range, then return `max(robLinear(0, n-2), robLinear(1, n-1))`. Guard `n == 1` up front so neither range is empty. **The mental shift: compose, don't reinvent.** The optimal House Robber I is a five-line rolling loop. The circular version needs *nothing new* algorithmically — it just calls that loop twice over two ranges. Recognizing that the hard problem is two instances of the easy one is the entire interview signal here. **Why this stays O(1) space.** Each linear pass keeps only `rob1` and `rob2`; we never materialize a `dp[]` array, and the two passes run sequentially, reusing the same two variables. So memory is constant regardless of how many houses there are. **Why the single-house guard is non-negotiable.** With `n == 1`, the range `[0 .. n-2]` is `[0 .. -1]` and `[1 .. n-1]` is `[1 .. 0]` — both empty, so the helper would return 0 and you'd lose the lone house's money. Returning `nums[0]` before the split fixes it. (The two-house case is fine: ranges `[0..0]` and `[1..1]` correctly yield `max(nums[0], nums[1])`.) Time complexity: O(n). Space complexity: O(1).

LCPractice

Dynamic Programming · 5 of 44 · 9 min

You are a professional robber planning to rob houses along a street. This time the houses are arranged in a circle — the first and last houses are **adjacent** to each other.

As before, adjacent houses have connected security systems, so robbing two directly adjacent houses on the same night alerts the police.

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

In plain English

Same as House Robber — pick a max-money subset with no two adjacent houses — except the array is circular, so the first and last houses count as neighbors. The single new constraint is that houses 0 and n-1 can't both be chosen.

Examples

Example 1

Input: nums = [2, 3, 2]
Output: 3
Note: Can't rob houses 0 and 2 (now adjacent in the circle), so the best single choice is house 1 → 3.

Example 2

Input: nums = [1, 2, 3, 1]
Output: 4
Note: Rob house 0 (1) and house 2 (3) → 4. They aren't adjacent even in the circle.

Example 3

Input: nums = [1, 2, 3]
Output: 3
Note: Rob just house 2 → 3. Houses 0 and 2 conflict, so we can't take 1 + 3.

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 1000

Clarifying questions4First question: Are the first and last houses really adjacent?Explore questions

Q1.Are the first and last houses really adjacent?
Yes — that's the whole difference from House Robber I. Robbing house 0 forbids house n-1 and vice versa.
Q2.What if there's only one house?
Return nums[0]. With n == 1 there's no neighbor to conflict with, and the two-range reduction would produce empty ranges, so special-case it.
Q3.What about two houses?
They're adjacent in a circle, so rob the larger one: max(nums[0], nums[1]). The two-range split handles this naturally.
Q4.Can money be zero?
Yes, values are 0..1000. A zero house never helps the total but still blocks its neighbors if 'robbed'.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The houses form a circle, so house 0 and house n-1 are now adjacent — you can't rob both. Split into two linear House Robber subproblems: one over houses [0 .. n-2] and one over [1 .. n-1], and return the larger. Each linear pass is the O(1)-space rolling-variable DP, so the whole thing is O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that the only new wrinkle is the 0↔n-1 adjacency, and reduce the circular problem to two calls of the linear solver rather than inventing a fragile circular recurrence.

Where candidates slip

Trying to handle the wrap-around inside a single DP pass (off-by-one nightmares), or forgetting the n == 1 special case where both ranges are empty.

How to stand out

State the reduction crisply — 'fix whether house 0 is robbable, that breaks the cycle into two linear runs' — reuse the O(1) linear solver, and call out the single-house edge case before being asked.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion With Endpoint Cases	`O(2ⁿ)`	`O(n)`	Say this first to expose how the circle splits into two open-ended cases, then flag the exponential recursion before optimizing.	Read
2	Top-Down Memoization	`O(n)`	`O(n)`	The fix once the overlap is named — 'cache each suffix within a range so each linear pass is O(n)'.	Read
3	Bottom-Up — Two Linear Passes, Two Variables Each (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'reuse the O(1) linear House Robber on two ranges and take the max'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMax loot in a CIRCLE of housesOnly one house?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion With Endpoint Cases

TimeO(2ⁿ)SpaceO(n)

Say this first to expose how the circle splits into two open-ended cases, then flag the exponential recursion before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The only new rule is that houses 0 and n-1 are adjacent. What if you simply forbade one of them up front?

2Hint 2Explore hint

Case A: pretend house 0 doesn't exist → rob the line [1 .. n-1]. Case B: pretend house n-1 doesn't exist → rob the line [0 .. n-2]. The circle can't beat both.

3Hint 3Explore hint

For each case, recurse exactly like linear House Robber: rob(i) = max(nums[i] + rob(i+2), rob(i+1)) bounded by that case's range.

A · Core idea

The circular constraint sounds scary, but it collapses to a single observation: in any valid plan, house 0 and house n-1 are never both robbed. So enumerate the two ways to honor that: either we leave house 0 out (and the remaining houses 1 .. n-1 form a straight line) or we leave house n-1 out (houses 0 .. n-2 form a straight line). The optimal circular answer is the better of these two linear answers.

The mental shift: break the cycle by fixing an endpoint. A ring is hard because the two ends wrap into each other. The instant you force one end to be excluded, the wrap-around disappears and you're left with the plain line problem you already know how to solve. Two cases cover every possibility because at least one end must be missing.

Why two cases, not three. You might worry about the plan that robs neither end — but that plan is already a sub-case of both ranges, so it's covered. There's no scenario that escapes both [0 .. n-2] and [1 .. n-1].

Why we don't ship this. Each linear recursion overlaps subproblems exponentially, exactly like House Robber I. Name the reduction, then cache it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 2, 3, 1]

Case A range [0..2]

linear rob on [1,2,3] → max is rob 0 & 2 = 1+3

StatecaseA = 4

Final result4

C · Code with teaching comments

Reference implementation previewpublic int rob(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; }Explore the full code

solution.javaJava

Brute Force — Recursion With Endpoint Cases — reference

3 teaching notes

1
public int rob(int[] nums) {
2
    int n = nums.length;
3
    // Single house has no neighbor — return it directly. Both ranges below would be
4
    // empty otherwise.
5
    if (n == 1) {
6
        return nums[0];
7
    }
8
    // The reduction: best of 'drop last house' vs 'drop first house'. This line IS the
9
    // circular insight.
10
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
11
}
12
 
13
private int robRange(int[] nums, int lo, int hi) {
14
    return robFrom(nums, lo, hi);
15
}
16
 
17
private int robFrom(int[] nums, int i, int hi) {
18
    if (i > hi) {
19
        return 0;
20
    }
21
    // Standard linear take/skip; the +2 jump enforces 'no adjacent' within the range.
22
    int robThis = nums[i] + robFrom(nums, i + 2, hi);
23
    int skipThis = robFrom(nums, i + 1, hi);
24
    return Math.max(robThis, skipThis);
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

The reduction is the whole trick: a closed loop with conflicting ends becomes two open lines, each missing one end. Solving the harder problem by calling the easier one twice is a reusable move — it shows you'd rather compose known solutions than reinvent a brittle special case.

ComplexityO(2ⁿ) time, O(n) space — Each linear recursion branches into two per house → ~2ⁿ nodes, and we run it twice (still O(2ⁿ)). Recursion depth O(n) for the stack.

E · Edge cases and pitfalls4nums = [5] — n == 1 guard returns 5 immediately, avoiding the empty-range reduction.Explore edge cases

Edge cases handled

nums = [5]n == 1 guard returns 5 immediately, avoiding the empty-range reduction.

Pitfalls

Forgetting the n == 1 guard — both ranges (0..-1 and 1..0) are empty and you'd return 0 instead of nums[0].
Using ranges that overlap on both ends (e.g. [0..n-1] for both) — reintroduces the 0↔n-1 conflict.
Shipping the recursion — it's still exponential per range.

03.2

Approach 2 of 3

Top-Down Memoization

TimeO(n)SpaceO(n)

The fix once the overlap is named — 'cache each suffix within a range so each linear pass is O(n)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Within a single range, rob(i) returns the same value every time. Cache it.

2Hint 2Explore hint

Run memoized linear House Robber twice — once per range — with a fresh memo for each so indices don't collide between passes.

3Hint 3Explore hint

memo[i] = max(nums[i] + solve(i+2), solve(i+1)), bounded by the range's hi.

A · Core idea

Keep the two-range reduction, but memoize each linear pass so the exponential recursion becomes linear. For a given range, solve(i) caches the best loot achievable from house i to the range's end; the second time that suffix is needed it's a free read.

The mental shift: memoize the inner problem, not the outer split. The circular reduction is just two independent linear problems. We don't memoize across the split — each pass gets its own cache because index i means different things relative to each range. Inside a pass, the optimization is identical to House Robber I: cache solve(i) once.

Why a fresh cache per range. If both passes shared one memo, an answer computed for range [0 .. n-2] could be wrongly reused for range [1 .. n-1], where the boundaries differ. Resetting the cache (or keying it by range) keeps the two passes correct and independent.

Why the sentinel is -1. Money can be 0, so 0 is a valid cached answer. Use -1 to mark 'not computed' so a genuine zero suffix isn't mistaken for a cache miss.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [2, 3, 2]

A: solve(1)

max(3 + 0, 0) = 3, store

StatememoA[1] = 3

Final result3

C · Code with teaching comments

Reference implementation previewpublic int rob(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; }Explore the full code

solution.javaJava

Top-Down Memoization — reference

3 teaching notes

1
public int rob(int[] nums) {
2
    int n = nums.length;
3
    if (n == 1) {
4
        return nums[0];
5
    }
6
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
7
}
8
 
9
private int robRange(int[] nums, int lo, int hi) {
10
    // Fresh cache per range — indices must not be reused across the two passes with
11
    // different boundaries.
12
    int[] memo = new int[nums.length];
13
    Arrays.fill(memo, -1);
14
    return solve(nums, lo, hi, memo);
15
}
16
 
17
private int solve(int[] nums, int i, int hi, int[] memo) {
18
    if (i > hi) {
19
        return 0;
20
    }
21
    // Cache hit returns the suffix answer in O(1), collapsing the exponential recursion
22
    // to linear.
23
    if (memo[i] != -1) {
24
        return memo[i];
25
    }
26
    int robThis = nums[i] + solve(nums, i + 2, hi, memo);
27
    int skipThis = solve(nums, i + 1, hi, memo);
28
    // Store the best loot from i to hi before returning.
29
    memo[i] = Math.max(robThis, skipThis);
30
    return memo[i];
31
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.31 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Memoization here is layered on top of a reduction: solve the circle by reducing to lines, then make each line fast with a cache. Composing a problem-shape reduction with a standard speed-up is a very common interview move — recognize the sub-problem, then apply the textbook optimization to it.

ComplexityO(n) time, O(n) space — Each range has at most n distinct subproblems solved once in O(1) → O(n) per pass, two passes → O(n) total. O(n) for the memo and recursion stack.

E · Edge cases and pitfalls5nums = [1, 2] — Range A = [0..0] → 1, Range B = [1..1] → 2, max = 2. Two adjacent circular houses, pick the bigger.Explore edge cases

Edge cases handled

nums = [1, 2]Range A = [0..0] → 1, Range B = [1..1] → 2, max = 2. Two adjacent circular houses, pick the bigger.
nums = [0, 0, 0]All zeros; the -1 sentinel keeps real zero answers distinct from misses, result 0.

Pitfalls

Sharing one memo across both ranges — cross-contaminates answers with different boundaries.
Using 0 as the uncomputed sentinel — collides with legitimate zero loot.
Dropping the n == 1 guard — empty ranges return 0.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — Two Linear Passes, Two Variables Each (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'reuse the O(1) linear House Robber on two ranges and take the max'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already have the O(1) rolling-variable linear House Robber. How many times do you need to call it for the circle?

2Hint 2Explore hint

Call it once on houses [0 .. n-2] and once on [1 .. n-1], then return the max. Don't allocate any DP array.

3Hint 3Explore hint

Each call keeps just rob1 and rob2; the single-house case returns nums[0] before the split.

A · Core idea

Combine the reduction with the constant-space linear solver. Write a helper robLinear(lo, hi) that runs the familiar two-variable House Robber over an index range, then return max(robLinear(0, n-2), robLinear(1, n-1)). Guard n == 1 up front so neither range is empty.

The mental shift: compose, don't reinvent. The optimal House Robber I is a five-line rolling loop. The circular version needs nothing new algorithmically — it just calls that loop twice over two ranges. Recognizing that the hard problem is two instances of the easy one is the entire interview signal here.

Why this stays O(1) space. Each linear pass keeps only rob1 and rob2; we never materialize a dp[] array, and the two passes run sequentially, reusing the same two variables. So memory is constant regardless of how many houses there are.

Why the single-house guard is non-negotiable. With n == 1, the range [0 .. n-2] is [0 .. -1] and [1 .. n-1] is [1 .. 0] — both empty, so the helper would return 0 and you'd lose the lone house's money. Returning nums[0] before the split fixes it. (The two-house case is fine: ranges [0..0] and [1..1] correctly yield max(nums[0], nums[1]).)

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [2, 3, 2]

Array state

Case A: range [0..2]

drop house 3 — rob a line of [1,2,3]

lo ↓

[0]

[1]

hi ↓

[2]

[3]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Bottom-Up — Two Linear Passes, Two Variables Each (Optimal) — optimal

4 teaching notes

1
public int rob(int[] nums) {
2
    int n = nums.length;
3
    // Single house must be returned directly — both ranges below would be empty and
4
    // lose its money.
5
    if (n == 1) {
6
        return nums[0];
7
    }
8
    // Break the circle: best of excluding the last house vs excluding the first. The
9
    // core circular idea in one line.
10
    return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
11
}
12
 
13
private int robLinear(int[] nums, int lo, int hi) {
14
    int rob1 = 0, rob2 = 0;
15
    for (int i = lo; i <= hi; i++) {
16
        // Identical linear recurrence: skip (rob2) vs rob this house (rob1 + value),
17
        // where rob1 excludes the previous house.
18
        int newRob = Math.max(rob2, rob1 + nums[i]);
19
        // Slide the window forward before overwriting rob2 — same order discipline as
20
        // linear House Robber.
21
        rob1 = rob2;
22
        rob2 = newRob;
23
    }
24
    return rob2;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The constant-space trick from House Robber I carries over untouched — the circle only adds an outer 'try both endpoint exclusions' wrapper. When a follow-up adds a global constraint to a problem you've solved, ask whether you can express the constraint as a small set of restricted re-runs rather than a brand-new algorithm. That reframing turns 'medium' circular problems into two 'easy' linear ones.

ComplexityO(n) time, O(1) space — Two linear scans, each O(n) with O(1) work per house → O(n) time. Each scan keeps two integers → O(1) space overall.

E · Edge cases and pitfalls5nums = [1, 2] — Ranges [0..0] → 1 and [1..1] → 2; max = 2. Adjacent circular pair handled by the split.Explore edge cases

Edge cases handled

nums = [1, 2]Ranges [0..0] → 1 and [1..1] → 2; max = 2. Adjacent circular pair handled by the split.
nums = [200, 3, 140, 20, 10]Case A (drop last) lets you rob 200 + 140 = 340; Case B can't pair with 200's neighbor as well. Returns 340.

Pitfalls

Omitting the n == 1 guard — both ranges empty, returns 0 instead of the single house.
Building a full dp array per pass — wastes the O(1) space the rolling variables give you.
Returning rob1 instead of rob2 from robLinear — off-by-one excluding the last house in the range.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int rob(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Ignoring the circular adjacency

Running plain linear House Robber lets you rob both house 0 and house n-1, which the circle forbids. On [2,3,2] it would return 4 instead of 3.

Explore the code comparison

Don't write this

return rob_linear(0, n - 1)

Write this instead

return max(rob_linear(0, n - 2), rob_linear(1, n - 1))

Missing the single-house guard

With n == 1 the ranges [0 .. n-2] and [1 .. n-1] are both empty, so the helper returns 0 and the lone house's money is lost.

Explore the code comparison

Don't write this

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

Write this instead

if (n == 1) {
    return nums[0];
}
return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));

Overlapping both endpoints in a range

If either range spans the full [0 .. n-1], the 0↔n-1 conflict comes back. Each range must exclude exactly one endpoint.

Explore the code comparison

Don't write this

int a = robLinear(nums, 0, n - 1);
int b = robLinear(nums, 0, n - 1);

Write this instead

int a = robLinear(nums, 0, n - 2);
int b = robLinear(nums, 1, n - 1);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Circular 1D DP — reduce to two linear runs

Code pattern to memorize

if n == 1: return nums[0]
return max(robLinear(nums, 0, n-2), robLinear(nums, 1, n-1))
# robLinear is the standard rolling-variable House Robber

Rules to remember

1The circle makes house 0 and house n-1 adjacent — they can never both be robbed.
2Break the cycle by FIXING the choice on house 0: either it's out (consider [1 .. n-1]) or the last house is out (consider [0 .. n-2]).
3Run the linear House Robber on each range and take the max — never write a special circular recurrence.
4Single-house input is the trap: with n == 1 both ranges are empty, so special-case it to return nums[0].
5Each linear pass is the same rob1/rob2 rolling-variable DP — O(1) space, reused twice.

Use this pattern when

House Robber constraints, but the line is closed into a ring
A circular-array DP where the two endpoints conflict with each other
You can remove the wrap-around by fixing one endpoint's inclusion
Any 'cannot pick both ends' constraint that splits cleanly into two open cases

Choose another pattern when

Houses are a straight line → plain House Robber, no split needed
Houses form a tree → House Robber III, post-order DP
More than two endpoints interact → the two-range trick won't cover all cases
You're counting circular arrangements, not maximizing → a different combinatorial DP

Interview takeaway

House Robber II teaches the canonical 'break the circle' move: a ring constraint where two ends conflict reduces to two linear problems with one end excluded each. Solve the hard variant by reusing the easy one twice — a reduction pattern that recurs all over circular-array DP.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCircular 1D Dynamic Programming — reduce a ring to two linear runs by excluding one conflicting endpoint each. Recognize it whenever two array endpoints interact. Built directly on top of linear House Robber.

Practice queueDirect variations and pattern siblings

Direct follow-ups

House Robber
The linear base case this problem reduces to — solve it first, then call it twice.
House Robber III
Coming soon
Houses form a binary tree; post-order DP returns (rob, skip) for each node.
Delete and Earn
Coming soon
Bucket by value, then it's linear House Robber on the value axis.
Circular array max-sum problems
Same 'break the circle into two linear cases' reduction reappears for circular subarray sums.

Same pattern

←

House Robber

Continue · Next problem

Longest Palindromic Substring

mediumDynamic ProgrammingLC #213Sometimes asked

House Robber II

LCPractice

Dynamic Programming · 5 of 44 · 9 min

You are a professional robber planning to rob houses along a street. This time the houses are arranged in a circle — the first and last houses are **adjacent** to each other.

As before, adjacent houses have connected security systems, so robbing two directly adjacent houses on the same night alerts the police.

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

In plain English

Examples

Example 1

Input: nums = [2, 3, 2]
Output: 3
Note: Can't rob houses 0 and 2 (now adjacent in the circle), so the best single choice is house 1 → 3.

Example 2

Input: nums = [1, 2, 3, 1]
Output: 4
Note: Rob house 0 (1) and house 2 (3) → 4. They aren't adjacent even in the circle.

Example 3

Input: nums = [1, 2, 3]
Output: 3
Note: Rob just house 2 → 3. Houses 0 and 2 conflict, so we can't take 1 + 3.

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 1000

Clarifying questions4First question: Are the first and last houses really adjacent?Explore questions

Q1.Are the first and last houses really adjacent?
Yes — that's the whole difference from House Robber I. Robbing house 0 forbids house n-1 and vice versa.
Q2.What if there's only one house?
Return nums[0]. With n == 1 there's no neighbor to conflict with, and the two-range reduction would produce empty ranges, so special-case it.
Q3.What about two houses?
They're adjacent in a circle, so rob the larger one: max(nums[0], nums[1]). The two-range split handles this naturally.
Q4.Can money be zero?
Yes, values are 0..1000. A zero house never helps the total but still blocks its neighbors if 'robbed'.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that the only new wrinkle is the 0↔n-1 adjacency, and reduce the circular problem to two calls of the linear solver rather than inventing a fragile circular recurrence.

Where candidates slip

Trying to handle the wrap-around inside a single DP pass (off-by-one nightmares), or forgetting the n == 1 special case where both ranges are empty.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion With Endpoint Cases	`O(2ⁿ)`	`O(n)`	Say this first to expose how the circle splits into two open-ended cases, then flag the exponential recursion before optimizing.	Read
2	Top-Down Memoization	`O(n)`	`O(n)`	The fix once the overlap is named — 'cache each suffix within a range so each linear pass is O(n)'.	Read
3	Bottom-Up — Two Linear Passes, Two Variables Each (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'reuse the O(1) linear House Robber on two ranges and take the max'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion With Endpoint Cases

TimeO(2ⁿ)SpaceO(n)

Say this first to expose how the circle splits into two open-ended cases, then flag the exponential recursion before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The only new rule is that houses 0 and n-1 are adjacent. What if you simply forbade one of them up front?

2Hint 2Explore hint

Case A: pretend house 0 doesn't exist → rob the line [1 .. n-1]. Case B: pretend house n-1 doesn't exist → rob the line [0 .. n-2]. The circle can't beat both.

3Hint 3Explore hint

For each case, recurse exactly like linear House Robber: rob(i) = max(nums[i] + rob(i+2), rob(i+1)) bounded by that case's range.

A · Core idea

Why we don't ship this. Each linear recursion overlaps subproblems exponentially, exactly like House Robber I. Name the reduction, then cache it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 2, 3, 1]

Case A range [0..2]

linear rob on [1,2,3] → max is rob 0 & 2 = 1+3

StatecaseA = 4

Final result4

C · Code with teaching comments

Reference implementation previewpublic int rob(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; }Explore the full code

solution.javaJava

Brute Force — Recursion With Endpoint Cases — reference

3 teaching notes

1
public int rob(int[] nums) {
2
    int n = nums.length;
3
    // Single house has no neighbor — return it directly. Both ranges below would be
4
    // empty otherwise.
5
    if (n == 1) {
6
        return nums[0];
7
    }
8
    // The reduction: best of 'drop last house' vs 'drop first house'. This line IS the
9
    // circular insight.
10
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
11
}
12
 
13
private int robRange(int[] nums, int lo, int hi) {
14
    return robFrom(nums, lo, hi);
15
}
16
 
17
private int robFrom(int[] nums, int i, int hi) {
18
    if (i > hi) {
19
        return 0;
20
    }
21
    // Standard linear take/skip; the +2 jump enforces 'no adjacent' within the range.
22
    int robThis = nums[i] + robFrom(nums, i + 2, hi);
23
    int skipThis = robFrom(nums, i + 1, hi);
24
    return Math.max(robThis, skipThis);
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(2ⁿ) time, O(n) space — Each linear recursion branches into two per house → ~2ⁿ nodes, and we run it twice (still O(2ⁿ)). Recursion depth O(n) for the stack.

E · Edge cases and pitfalls4nums = [5] — n == 1 guard returns 5 immediately, avoiding the empty-range reduction.Explore edge cases

Edge cases handled

nums = [5]n == 1 guard returns 5 immediately, avoiding the empty-range reduction.

Pitfalls

Forgetting the n == 1 guard — both ranges (0..-1 and 1..0) are empty and you'd return 0 instead of nums[0].
Using ranges that overlap on both ends (e.g. [0..n-1] for both) — reintroduces the 0↔n-1 conflict.
Shipping the recursion — it's still exponential per range.

03.2

Approach 2 of 3

Top-Down Memoization

TimeO(n)SpaceO(n)

The fix once the overlap is named — 'cache each suffix within a range so each linear pass is O(n)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Within a single range, rob(i) returns the same value every time. Cache it.

2Hint 2Explore hint

Run memoized linear House Robber twice — once per range — with a fresh memo for each so indices don't collide between passes.

3Hint 3Explore hint

memo[i] = max(nums[i] + solve(i+2), solve(i+1)), bounded by the range's hi.

A · Core idea

Why the sentinel is -1. Money can be 0, so 0 is a valid cached answer. Use -1 to mark 'not computed' so a genuine zero suffix isn't mistaken for a cache miss.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [2, 3, 2]

A: solve(1)

max(3 + 0, 0) = 3, store

StatememoA[1] = 3

Final result3

C · Code with teaching comments

Reference implementation previewpublic int rob(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; }Explore the full code

solution.javaJava

Top-Down Memoization — reference

3 teaching notes

1
public int rob(int[] nums) {
2
    int n = nums.length;
3
    if (n == 1) {
4
        return nums[0];
5
    }
6
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
7
}
8
 
9
private int robRange(int[] nums, int lo, int hi) {
10
    // Fresh cache per range — indices must not be reused across the two passes with
11
    // different boundaries.
12
    int[] memo = new int[nums.length];
13
    Arrays.fill(memo, -1);
14
    return solve(nums, lo, hi, memo);
15
}
16
 
17
private int solve(int[] nums, int i, int hi, int[] memo) {
18
    if (i > hi) {
19
        return 0;
20
    }
21
    // Cache hit returns the suffix answer in O(1), collapsing the exponential recursion
22
    // to linear.
23
    if (memo[i] != -1) {
24
        return memo[i];
25
    }
26
    int robThis = nums[i] + solve(nums, i + 2, hi, memo);
27
    int skipThis = solve(nums, i + 1, hi, memo);
28
    // Store the best loot from i to hi before returning.
29
    memo[i] = Math.max(robThis, skipThis);
30
    return memo[i];
31
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.31 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Each range has at most n distinct subproblems solved once in O(1) → O(n) per pass, two passes → O(n) total. O(n) for the memo and recursion stack.

E · Edge cases and pitfalls5nums = [1, 2] — Range A = [0..0] → 1, Range B = [1..1] → 2, max = 2. Two adjacent circular houses, pick the bigger.Explore edge cases

Edge cases handled

nums = [1, 2]Range A = [0..0] → 1, Range B = [1..1] → 2, max = 2. Two adjacent circular houses, pick the bigger.
nums = [0, 0, 0]All zeros; the -1 sentinel keeps real zero answers distinct from misses, result 0.

Pitfalls

Sharing one memo across both ranges — cross-contaminates answers with different boundaries.
Using 0 as the uncomputed sentinel — collides with legitimate zero loot.
Dropping the n == 1 guard — empty ranges return 0.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — Two Linear Passes, Two Variables Each (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'reuse the O(1) linear House Robber on two ranges and take the max'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already have the O(1) rolling-variable linear House Robber. How many times do you need to call it for the circle?

2Hint 2Explore hint

Call it once on houses [0 .. n-2] and once on [1 .. n-1], then return the max. Don't allocate any DP array.

3Hint 3Explore hint

Each call keeps just rob1 and rob2; the single-house case returns nums[0] before the split.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [2, 3, 2]

Array state

Case A: range [0..2]

drop house 3 — rob a line of [1,2,3]

lo ↓

[0]

[1]

hi ↓

[2]

[3]

Current pointerResolved stateNot processed

Final result3

C · Code with teaching comments

solution.javaJava

Bottom-Up — Two Linear Passes, Two Variables Each (Optimal) — optimal

4 teaching notes

1
public int rob(int[] nums) {
2
    int n = nums.length;
3
    // Single house must be returned directly — both ranges below would be empty and
4
    // lose its money.
5
    if (n == 1) {
6
        return nums[0];
7
    }
8
    // Break the circle: best of excluding the last house vs excluding the first. The
9
    // core circular idea in one line.
10
    return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
11
}
12
 
13
private int robLinear(int[] nums, int lo, int hi) {
14
    int rob1 = 0, rob2 = 0;
15
    for (int i = lo; i <= hi; i++) {
16
        // Identical linear recurrence: skip (rob2) vs rob this house (rob1 + value),
17
        // where rob1 excludes the previous house.
18
        int newRob = Math.max(rob2, rob1 + nums[i]);
19
        // Slide the window forward before overwriting rob2 — same order discipline as
20
        // linear House Robber.
21
        rob1 = rob2;
22
        rob2 = newRob;
23
    }
24
    return rob2;
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — Two linear scans, each O(n) with O(1) work per house → O(n) time. Each scan keeps two integers → O(1) space overall.

E · Edge cases and pitfalls5nums = [1, 2] — Ranges [0..0] → 1 and [1..1] → 2; max = 2. Adjacent circular pair handled by the split.Explore edge cases

Edge cases handled

nums = [1, 2]Ranges [0..0] → 1 and [1..1] → 2; max = 2. Adjacent circular pair handled by the split.
nums = [200, 3, 140, 20, 10]Case A (drop last) lets you rob 200 + 140 = 340; Case B can't pair with 200's neighbor as well. Returns 340.

Pitfalls

Omitting the n == 1 guard — both ranges empty, returns 0 instead of the single house.
Building a full dp array per pass — wastes the O(1) space the rolling variables give you.
Returning rob1 instead of rob2 from robLinear — off-by-one excluding the last house in the range.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int rob(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Ignoring the circular adjacency

Running plain linear House Robber lets you rob both house 0 and house n-1, which the circle forbids. On [2,3,2] it would return 4 instead of 3.

Explore the code comparison

Don't write this

return rob_linear(0, n - 1)

Write this instead

return max(rob_linear(0, n - 2), rob_linear(1, n - 1))

Missing the single-house guard

With n == 1 the ranges [0 .. n-2] and [1 .. n-1] are both empty, so the helper returns 0 and the lone house's money is lost.

Explore the code comparison

Don't write this

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

Write this instead

if (n == 1) {
    return nums[0];
}
return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));

Overlapping both endpoints in a range

If either range spans the full [0 .. n-1], the 0↔n-1 conflict comes back. Each range must exclude exactly one endpoint.

Explore the code comparison

Don't write this

int a = robLinear(nums, 0, n - 1);
int b = robLinear(nums, 0, n - 1);

Write this instead

int a = robLinear(nums, 0, n - 2);
int b = robLinear(nums, 1, n - 1);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Circular 1D DP — reduce to two linear runs

Code pattern to memorize

if n == 1: return nums[0]
return max(robLinear(nums, 0, n-2), robLinear(nums, 1, n-1))
# robLinear is the standard rolling-variable House Robber

Rules to remember

1The circle makes house 0 and house n-1 adjacent — they can never both be robbed.
2Break the cycle by FIXING the choice on house 0: either it's out (consider [1 .. n-1]) or the last house is out (consider [0 .. n-2]).
3Run the linear House Robber on each range and take the max — never write a special circular recurrence.
4Single-house input is the trap: with n == 1 both ranges are empty, so special-case it to return nums[0].
5Each linear pass is the same rob1/rob2 rolling-variable DP — O(1) space, reused twice.

Use this pattern when

House Robber constraints, but the line is closed into a ring
A circular-array DP where the two endpoints conflict with each other
You can remove the wrap-around by fixing one endpoint's inclusion
Any 'cannot pick both ends' constraint that splits cleanly into two open cases

Choose another pattern when

Houses are a straight line → plain House Robber, no split needed
Houses form a tree → House Robber III, post-order DP
More than two endpoints interact → the two-range trick won't cover all cases
You're counting circular arrangements, not maximizing → a different combinatorial DP

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

House Robber
The linear base case this problem reduces to — solve it first, then call it twice.
House Robber III
Coming soon
Houses form a binary tree; post-order DP returns (rob, skip) for each node.
Delete and Earn
Coming soon
Bucket by value, then it's linear House Robber on the value axis.
Circular array max-sum problems
Same 'break the circle into two linear cases' reduction reappears for circular subarray sums.

Same pattern

←

House Robber

Continue · Next problem

Longest Palindromic Substring