House Robber II — Handling the Circular Constraint with Two Linear Passes

Problem Statement

You are a professional robber planning to rob houses along a street. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. 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.

Constraints:

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

Example 1:

Input:  nums = [2, 3, 2]
Output: 3
Explanation: Cannot rob house 1 (2) then house 3 (2) since they are adjacent in the circle.
             Best: rob only house 2 for 3.

Example 2:

Input:  nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 1 (1) then house 3 (3). Total = 4.

Example 3:

Input:  nums = [1, 2, 3]
Output: 3
Explanation: Rob house 3 (3). Cannot rob houses 1 and 3 together (adjacent in circle).

Why This Problem Matters

House Robber II is one of the most elegant "constraint upgrade" problems in dynamic programming. It takes the classic House Robber skip-one DP you already know and adds a single constraint — the array is circular — that appears to break everything. The insight that resolves it is clean and memorable: since house 0 and house n-1 cannot both be robbed, split the problem into two non-circular subproblems and take the best.

This problem appears at Amazon, Google, and Bloomberg interviews specifically because it tests systematic problem decomposition. You must recognize that the circular constraint reduces to a case analysis, not a new algorithm. Candidates who try to modify the recurrence directly tend to get tangled; those who see the decomposition solve it cleanly in minutes.

It also reinforces code reuse — a mature engineering habit: instead of writing one complex function, write one simple helper and call it twice.

The Core Insight

In a circle of n houses, house 0 and house n-1 are neighbors. When you choose your robbing strategy, exactly one of three things is true:

You rob neither house 0 nor house n-1.
You rob house 0 but not house n-1.
You rob house n-1 but not house 0.

Cases 2 and 3 already subsume case 1 (their optimal solutions may also skip both ends). So it suffices to solve:

Subproblem A: Rob houses 0 through n-2 (exclude the last house).
Subproblem B: Rob houses 1 through n-1 (exclude the first house).

Each subproblem is a standard linear House Robber problem. Return max(A, B).

Why this is correct: Any optimal circular solution either includes house 0 or it does not. If it includes house 0, it cannot include house n-1, so it is a valid solution to Subproblem A (which includes house 0 but not n-1). If it excludes house 0, it is a valid solution to Subproblem B. Taking the max over both subproblems covers both cases.

Building the DP Solution

Helper: Linear House Robber

# Python — linear rob helper
def rob_linear(arr):
    prev2, prev1 = 0, 0
    for num in arr:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

// JavaScript — linear rob helper
function robLinear(nums, lo, hi) {
    let prev2 = 0, prev1 = 0;
    for (let i = lo; i <= hi; i++) {
        [prev2, prev1] = [prev1, Math.max(prev1, prev2 + nums[i])];
    }
    return prev1;
}

Step 1 — Naive Recursive Approach

# Python — naive recursion with case split (memoized internally)
from functools import lru_cache
 
def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
 
    def solve(lo, hi):
        @lru_cache(maxsize=None)
        def dp(i):
            if i < lo:
                return 0
            if i == lo:
                return nums[lo]
            return max(dp(i - 1), dp(i - 2) + nums[i])
        return dp(hi)
 
    return max(solve(0, n - 2), solve(1, n - 1))

Step 2 — Top-Down Memoization

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
 
        def solve(start: int, end: int) -> int:
            @lru_cache(maxsize=None)
            def dp(i: int) -> int:
                if i < start:
                    return 0
                if i == start:
                    return nums[start]
                return max(dp(i - 1), dp(i - 2) + nums[i])
            return dp(end)
 
        return max(solve(0, n - 2), solve(1, n - 1))

// JavaScript — top-down memoization
var rob = function(nums) {
    const n = nums.length;
    if (n === 1) return nums[0];
 
    function solve(lo, hi) {
        const memo = new Map();
        function dp(i) {
            if (i < lo) return 0;
            if (i === lo) return nums[lo];
            if (memo.has(i)) return memo.get(i);
            const result = Math.max(dp(i - 1), dp(i - 2) + nums[i]);
            memo.set(i, result);
            return result;
        }
        return dp(hi);
    }
 
    return Math.max(solve(0, n - 2), solve(1, n - 1));
};

Step 3 — Bottom-Up Tabulation with Helper

# Python — bottom-up tabulation
class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
 
        def rob_range(arr: list[int]) -> int:
            prev2, prev1 = 0, 0
            for num in arr:
                prev2, prev1 = prev1, max(prev1, prev2 + num)
            return prev1
 
        return max(rob_range(nums[:-1]), rob_range(nums[1:]))

// JavaScript — bottom-up tabulation
var rob = function(nums) {
    const n = nums.length;
    if (n === 1) return nums[0];
 
    function robRange(lo, hi) {
        let prev2 = 0, prev1 = 0;
        for (let i = lo; i <= hi; i++) {
            [prev2, prev1] = [prev1, Math.max(prev1, prev2 + nums[i])];
        }
        return prev1;
    }
 
    return Math.max(robRange(0, n - 2), robRange(1, n - 1));
};

Optimized Solution

The space-optimized solution is already achieved in the tabulation version above. Each linear pass uses O(1) space, and we run two passes. Total space: O(1).

# Python — final clean solution, O(n) time, O(1) space
class Solution:
    def rob(self, nums: list[int]) -> int:
        if len(nums) == 1:
            return nums[0]
 
        def rob_linear(arr: list[int]) -> int:
            prev2, prev1 = 0, 0
            for num in arr:
                prev2, prev1 = prev1, max(prev1, prev2 + num)
            return prev1
 
        return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

// JavaScript — final clean solution, O(n) time, O(1) space
var rob = function(nums) {
    const n = nums.length;
    if (n === 1) return nums[0];
 
    function robLinear(lo, hi) {
        let prev2 = 0, prev1 = 0;
        for (let i = lo; i <= hi; i++) {
            [prev2, prev1] = [prev1, Math.max(prev1, prev2 + nums[i])];
        }
        return prev1;
    }
 
    return Math.max(robLinear(0, n - 2), robLinear(1, n - 1));
};

Visual Dry Run

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

Subproblem A: nums[0..2] = [1, 2, 3] (exclude last house)

num	prev2	prev1	new prev1 = max(prev1, prev2+num)
1	0	0	max(0, 0+1) = 1
2	0	1	max(1, 0+2) = 2
3	1	2	max(2, 1+3) = 4

Result A = 4

Subproblem B: nums[1..3] = [2, 3, 1] (exclude first house)

num	prev2	prev1	new prev1 = max(prev1, prev2+num)
2	0	0	max(0, 0+2) = 2
3	0	2	max(2, 0+3) = 3
1	2	3	max(3, 2+1) = 3

Result B = 3

Answer = max(4, 3) = 4. Rob houses at index 0 (1) and index 2 (3).

Complexity Analysis

Approach	Time	Space	Notes
Two linear passes	O(n)	O(1)	Optimal — run helper twice
Top-down with memo	O(n)	O(n)	Memo table per subproblem
Bottom-up tabulation	O(n)	O(n)	Full dp array per subproblem

Common Mistakes

1. Forgetting to handle n = 1. With a single house, there is no circular neighbor issue — just return nums[0]. Without this guard, nums[:-1] returns an empty slice.

2. Handling n = 2 incorrectly. For [3, 1], Subproblem A is [3] (result 3) and Subproblem B is [1] (result 1). The answer is 3. The rolling variable approach handles this naturally.

3. Thinking three cases are needed. You might think: "rob neither end," "rob only start," "rob only end." In fact, solving nums[0..n-2] and nums[1..n-1] and taking the max already covers all three cases optimally. No third pass is needed.

4. Modifying the recurrence instead of decomposing. A common wrong approach is to add a flag can_rob_last to the recurrence. This works but is complex and error-prone. The two-pass decomposition is simpler, cleaner, and easier to explain.

5. Using slicing when index ranges suffice. nums[:-1] creates a new list (O(n) space). Passing index bounds lo and hi to the helper achieves O(1) extra space.

6. Not testing the circular adjacency. Test [2, 3, 2]: houses 0 (2) and 2 (2) are adjacent in the circle. The answer is 3 (rob house 1 only). A linear DP without the circular split would incorrectly return 4.

Interview Tips

Name the decomposition strategy. Say: "The circular constraint means house 0 and house n-1 are adjacent. I cannot include both. So I reduce the problem to two linear House Robber instances — one that includes house 0 (excludes the last), and one that excludes house 0 (includes the last) — and take the max."

Write the helper first. Start by coding the linear House Robber helper cleanly. Then the main function becomes two lines. This demonstrates code reuse and modularity — valued at all FAANG companies.

Prove correctness in one sentence. "Every optimal circular solution either includes house 0 or it doesn't. The two subproblems cover both cases, and taking the max gives the global optimum."

Mention the code reuse. "I'm reusing the linear robber helper from House Robber I — this is the kind of composability that makes complex problems manageable."

Follow-up Questions

Q: What if houses are arranged in a line but you cannot rob the first k or last k houses? Adjust the subproblem ranges accordingly: rob from index k to n-1-k. The same rolling-variable DP applies within that range.

Q: What if k rounds of robbing are allowed and each house resets after being robbed? This becomes a repeated-game variant. For k rounds, multiply the single-round answer by k (assuming optimal strategy is the same each round). If houses have different reset values, this needs more complex modeling.

Q: What is House Robber III? LC 337 arranges houses as a binary tree. At each node, rob it (and skip children) or skip it (and allow children). The tree DP returns a pair (rob, skip) from each subtree.

Q: What if the circle has a break at a random position? If the break is at position k, run the linear DP on nums[k..k+n-1] (modular indexing). The circular constraint is eliminated at the break point.

Q: What if you can rob at most m non-adjacent houses? Add a second DP dimension tracking the count of houses robbed so far. dp[i][j] = max stolen using the first i houses with exactly j robberies.

Key Takeaways

The circular constraint means house 0 and house n-1 cannot both be robbed. This reduces to two independent linear House Robber problems: one excluding the last house, one excluding the first.
Run the linear House Robber helper (O(n) time, O(1) space) twice and return the max of both results.
This two-pass decomposition is simpler than modifying the recurrence with flags or extra dimensions — always prefer decomposition over complication.
Always handle the edge case n = 1 before entering the decomposition logic.
The pattern generalizes: whenever a circular constraint blocks including both endpoints, split into two linear subproblems that exclude one endpoint each.
Demonstrating clean code reuse by factoring out the rob_linear helper is itself an interview signal about engineering habits.

Problem Statement#

Why This Problem Matters#

The Core Insight#

Building the DP Solution#

Helper: Linear House Robber#

Step 1 — Naive Recursive Approach#

Step 2 — Top-Down Memoization#

Step 3 — Bottom-Up Tabulation with Helper#

Optimized Solution#

Visual Dry Run#

Complexity Analysis#

Common Mistakes#

Interview Tips#

Follow-up Questions#

Key Takeaways#

Related reading