Skip to content

Volume ITechnology

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)

Restating the Problem: You are back in the same neighborhood, but this time the houses are arranged in a closed loop (a cul-de-sac). The very last house is right next door to the very first house. The alarm rule still applies: robbing any two adjacent houses will sound the alarm. What is the maximum amount of cash you can escape with?

Constraints to Note:

  • The array can have up to 100 houses.
  • House values are non-negative.
  • The array can have just 1 house, and because the street is circular, the first house is its own neighbor in a way, but since it's the only one, we just take it.

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:  # (1)
            return nums[0]                   # a single house has no neighbour

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

        return max(rob_line(nums[1:]),        # (5) skip the first
                   rob_line(nums[:-1]))       # skip the last
ts
function rob(nums: number[]): number {
  if (nums.length === 1) return nums[0];  // (1)

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

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

Line by line ​

The houses now stand in a circle, so the first and last houses are neighbours. They can never both be robbed.

(1) One house has no neighbour, so rob it. This line is needed. The note below shows what goes wrong without it.

(2) rob_line is the straight-street robber from 4.23.3, unchanged.

(3) The best totals up to two houses back and one house back.

(4) Rob this house or skip it, exactly as before.

(5) Break the circle in the two possible ways, and keep the better result. Either the first house is left out, so the rest is a straight street, nums[1:]. Or the last house is left out, nums[:-1]. Any valid plan leaves out at least one of the two, so it is counted by at least one of these two straight streets.

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:

python
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.

Trace ​

Let's trace nums = [2, 3, 2]. First, we bypass the n = 1 guard because n = 3. We make two calls to rob_line:

  1. rob_line(nums[1:]) which is [3, 2] (skip the first house).
    • Value 3: two = 0, one = 0 \rightarrow new one = max(3+0, 0) = 3
    • Value 2: two = 0, one = 3 \rightarrow new one = max(2+0, 3) = 3
    • Result: 3
  2. rob_line(nums[:-1]) which is [2, 3] (skip the last house).
    • Value 2: two = 0, one = 0 \rightarrow new one = max(2+0, 0) = 2
    • Value 3: two = 0, one = 2 \rightarrow new one = max(3+0, 2) = 3
    • Result: 3

Finally, we return max(3, 3) = 3.

Edge cases ​

  • One house. Line (1) returns it.
  • Two houses. They are neighbours. The two straight streets are [nums[1]] and [nums[0]], so the answer is the richer house.
  • Three houses. All three touch each other in a circle, so you can rob only one: the richest.

Complexity ​

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

Time Complexity Derivation: We call the linear DP solver exactly twice. The first call processes N-1 elements taking O(N-1) time. The second call also processes N-1 elements, taking O(N-1) time. In total, we do 2 \times (N-1) operations. Dropping the constants leaves us with exactly O(N) time.

Space Complexity Derivation: If we slice the array (nums[1:]), Python/TypeScript allocates a new array in memory, taking O(N) extra space. If we use the index-range version, we pass around just the integers lo and hi, and run the same O(1) constant-space solver from House Robber I, giving an overall space complexity of O(1).

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.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet