House Robber II (LeetCode 213)
Every house on this block stores a certain amount of cash, but the block forms a loop: house 0 sits right next to the final house, not just its immediate neighbors on either side. Any two neighboring houses share one alarm, so hitting both on the same night trips it.
Given the cash stashed in each house as nums, work out the largest total you can steal in one night while never picking two neighboring houses (remembering the first and last houses count as neighbors too).
Worked Examples
nums = [2,3,2]3nums = [1,2,3,1]4nums = [1,2,3]31 and 3 cannot both be taken; robbing just the house with 3 is best.⚖️Formal Constraints & Bounds
1 <= nums.length <= 1000 <= nums[i] <= 1000
Core Insight
Decomposing circular graphs into linear paths solves boundary constraints without custom edge logic.
Real-World Scenario & Production Applications
Ring topology network security scheduling, circular resource allocation.
Subproblems & Recurrence Decomposition3 Phases
Because House 1 and House N are adjacent, robbing both is illegal. Decouple the circular graph into two independent linear subproblems: House 0 to N-2 (exclude last) and House 1 to N-1 (exclude first).
# Decouple into two linear runs
loot_1 = rob_linear(nums[:-1]) # Exclude last house
loot_2 = rob_linear(nums[1:]) # Exclude first house
return max(loot_1, loot_2)Step-by-Step Execution Trace Table
| Slice | Houses Evaluated | Linear Max Money |
|---|---|---|
| Slice 1 (exclude last) | [2, 3] | 3 |
| Slice 2 (exclude first) | [3, 2] | 3 |
| Result | max(3, 3) | 3 |
| 1 | if len(nums) == 1: |
| 2 | return nums[0] |
| 3 | def rob_linear(arr): |
| 4 | rob1, rob2 = 0, 0 |
| 5 | for x in arr: |
| 6 | temp = max(rob2, rob1 + x) |
| 7 | rob1 = rob2 |
| 8 | rob2 = temp |
| 9 | return rob2 |
| 10 | return max(rob_linear(nums[:-1]), rob_linear(nums[1:])) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
In House Robber I, houses were arranged linearly: adjacent houses triggered alarms, leading to the state recurrence . In House Robber II, the houses are arranged in a circle, meaning the first house nums[0] and the last house nums[n-1] are neighbors. The core intuition is to resolve the cycle by decomposing the circular graph into two independent linear subproblems:
- Case A: Rob from House to House (guarantees House is never touched).
- Case B: Rob from House to House (guarantees House is never touched). The optimal answer is strictly .
🏟️ The Analogy: A Circular Necklace with a Locked Clasp
Imagine a circular necklace of valuable gems. If you pry two adjacent gems loose, an alarm sounds. The clasp connects Gem to Gem . To remove the circular dependency:
- You cut the clasp and forbid touching Gem . Now it's a straight linear string of gems from to .
- Separately, you forbid touching Gem . Now it's a straight linear string of gems from to . Since you can never legally take both Gem and Gem together, one of these two linear cuts is guaranteed to contain the best possible total.
🔑 Why It Works
Notice how cleanly the circular constraint collapses: by running standard -space House Robber I twice across two array slices, we solve a circular dynamic program with zero additional state complexity in time.
Single element input trap: Running two sub-slices
nums[:-1]andnums[1:]whenlen(nums) == 1. Both slices are empty ([]), causing the algorithm to return 0 instead ofnums[0]. Guardif len(nums) == 1: return nums[0].Attempting a three-way case split: Slices
nums[:-1](houses 0 to ) andnums[1:](houses 1 to ) fully cover all valid possibilities, including robbing neither. A 3-way split adds unnecessary complexity.Re-implementing linear robber twice: Copy-pasting the linear robber logic twice introduces silent divergence bugs; factor into a helper function
rob_linear(sub_array).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Circular adjacency constraints on linear dynamic programming problems.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: house 0 and house n-1 cannot be co-selected.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Complex circular edge tracking instead of clean array slicing.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Since the first and last houses are adjacent, you cannot rob both. I run linear House Robber twice: once on
nums[:-1](excluding last) and once onnums[1:](excluding first). The answer is the maximum of both. Runs inO(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Runs linear House Robber twice: once on nums[0..N-2] (ignoring last) and once on nums[1..N-1] (ignoring first). Takes max of both results. Total 2 * (N - 1) operations.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Stores 2 scalar variables per linear pass in O(1) space.
T(N) = 2 · O(N) = O(N)
Derivation Progression
max(rob(0 dots N-2), rob(1 dots N-1))
First and last houses cannot both be robbed, breaking circular dependency.
2 × (N-1) transitions
Runs standard House Robber on each sub-array.
O(N) total time
Constant factor of 2 over standard linear scan.
Variable Definitions
Total number of houses in the circular neighborhood
Memory Architecture & Bounds
O(1) Iterative
O(1) Scalar registers
O(1) Max loot integer
Boundary Best / Worst Cases
for N=1.
.
general case.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "houses arranged in a circle", "first house is neighbor of last". Circular constraint reduction: house 0 and house are adjacent, so we can NEVER rob both. A Senior SWE decomposes the circle into two standard linear House Robber subproblems: 1. Rob houses (exclude last) 2. Rob houses (exclude first).
. Time budget linear time.
Slicing an array of length 1 would pass empty arrays to the helper!
House Robber II (LeetCode 213)
Every house on this block stores a certain amount of cash, but the block forms a loop: house 0 sits right next to the final house, not just its immediate neighbors on either side. Any two neighboring houses share one alarm, so hitting both on the same night trips it.
Given the cash stashed in each house as nums, work out the largest total you can steal in one night while never picking two neighboring houses (remembering the first and last houses count as neighbors too).
Worked Examples
nums = [2,3,2]3nums = [1,2,3,1]4nums = [1,2,3]31 and 3 cannot both be taken; robbing just the house with 3 is best.⚖️Formal Constraints & Bounds
1 <= nums.length <= 1000 <= nums[i] <= 1000
Core Insight
Decomposing circular graphs into linear paths solves boundary constraints without custom edge logic.
Real-World Scenario & Production Applications
Ring topology network security scheduling, circular resource allocation.
Subproblems & Recurrence Decomposition3 Phases
Because House 1 and House N are adjacent, robbing both is illegal. Decouple the circular graph into two independent linear subproblems: House 0 to N-2 (exclude last) and House 1 to N-1 (exclude first).
# Decouple into two linear runs
loot_1 = rob_linear(nums[:-1]) # Exclude last house
loot_2 = rob_linear(nums[1:]) # Exclude first house
return max(loot_1, loot_2)Step-by-Step Execution Trace Table
| Slice | Houses Evaluated | Linear Max Money |
|---|---|---|
| Slice 1 (exclude last) | [2, 3] | 3 |
| Slice 2 (exclude first) | [3, 2] | 3 |
| Result | max(3, 3) | 3 |
| 1 | if len(nums) == 1: |
| 2 | return nums[0] |
| 3 | def rob_linear(arr): |
| 4 | rob1, rob2 = 0, 0 |
| 5 | for x in arr: |
| 6 | temp = max(rob2, rob1 + x) |
| 7 | rob1 = rob2 |
| 8 | rob2 = temp |
| 9 | return rob2 |
| 10 | return max(rob_linear(nums[:-1]), rob_linear(nums[1:])) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
In House Robber I, houses were arranged linearly: adjacent houses triggered alarms, leading to the state recurrence . In House Robber II, the houses are arranged in a circle, meaning the first house nums[0] and the last house nums[n-1] are neighbors. The core intuition is to resolve the cycle by decomposing the circular graph into two independent linear subproblems:
- Case A: Rob from House to House (guarantees House is never touched).
- Case B: Rob from House to House (guarantees House is never touched). The optimal answer is strictly .
🏟️ The Analogy: A Circular Necklace with a Locked Clasp
Imagine a circular necklace of valuable gems. If you pry two adjacent gems loose, an alarm sounds. The clasp connects Gem to Gem . To remove the circular dependency:
- You cut the clasp and forbid touching Gem . Now it's a straight linear string of gems from to .
- Separately, you forbid touching Gem . Now it's a straight linear string of gems from to . Since you can never legally take both Gem and Gem together, one of these two linear cuts is guaranteed to contain the best possible total.
🔑 Why It Works
Notice how cleanly the circular constraint collapses: by running standard -space House Robber I twice across two array slices, we solve a circular dynamic program with zero additional state complexity in time.
Single element input trap: Running two sub-slices
nums[:-1]andnums[1:]whenlen(nums) == 1. Both slices are empty ([]), causing the algorithm to return 0 instead ofnums[0]. Guardif len(nums) == 1: return nums[0].Attempting a three-way case split: Slices
nums[:-1](houses 0 to ) andnums[1:](houses 1 to ) fully cover all valid possibilities, including robbing neither. A 3-way split adds unnecessary complexity.Re-implementing linear robber twice: Copy-pasting the linear robber logic twice introduces silent divergence bugs; factor into a helper function
rob_linear(sub_array).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Circular adjacency constraints on linear dynamic programming problems.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: house 0 and house n-1 cannot be co-selected.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Complex circular edge tracking instead of clean array slicing.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Since the first and last houses are adjacent, you cannot rob both. I run linear House Robber twice: once on
nums[:-1](excluding last) and once onnums[1:](excluding first). The answer is the maximum of both. Runs inO(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Runs linear House Robber twice: once on nums[0..N-2] (ignoring last) and once on nums[1..N-1] (ignoring first). Takes max of both results. Total 2 * (N - 1) operations.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Stores 2 scalar variables per linear pass in O(1) space.
T(N) = 2 · O(N) = O(N)
Derivation Progression
max(rob(0 dots N-2), rob(1 dots N-1))
First and last houses cannot both be robbed, breaking circular dependency.
2 × (N-1) transitions
Runs standard House Robber on each sub-array.
O(N) total time
Constant factor of 2 over standard linear scan.
Variable Definitions
Total number of houses in the circular neighborhood
Memory Architecture & Bounds
O(1) Iterative
O(1) Scalar registers
O(1) Max loot integer
Boundary Best / Worst Cases
for N=1.
.
general case.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "houses arranged in a circle", "first house is neighbor of last". Circular constraint reduction: house 0 and house are adjacent, so we can NEVER rob both. A Senior SWE decomposes the circle into two standard linear House Robber subproblems: 1. Rob houses (exclude last) 2. Rob houses (exclude first).
. Time budget linear time.
Slicing an array of length 1 would pass empty arrays to the helper!