House Robber II LeetCode 213 — Circular DP

LeetCode 213 — House Robber II — is a direct extension of the classic House Robber problem. You are given an integer array nums representing the amount of money in each house along a street. The houses are arranged in a circle, meaning the first house and the last house are neighbors. You cannot rob two adjacent houses because it will alert the police. Find the maximum amount of money you can rob tonight without alerting the police.

The circular arrangement is the only difference from House Robber I (LeetCode 198). In the linear version, the first and last houses have no special relationship. Here they are adjacent, which means robbing house 0 forbids robbing house n-1 and vice versa. This single constraint is enough to invalidate the straightforward House Robber I recurrence applied to the full array.

The problem is rated Medium on LeetCode and is a frequent interview question at top tech companies. It tests whether you can identify that the circular constraint collapses into two independent linear problems — a key pattern in circular array dynamic programming. The solution runs in O(n) time and O(1) space.

House Robber I (LeetCode 198) solves a linear street: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The key recurrence says: at each house, either skip it and keep the best from the previous house, or rob it and add it to the best from two houses back. Because the street is linear, there is no constraint linking the first and last house.

In House Robber II, houses form a ring. The only new constraint is that house 0 and house n-1 are adjacent — you can't rob both. Every other adjacency constraint is identical to the linear version. So the circular problem reduces to: what is the best we can do if we definitively exclude house n-1 from consideration? What if we definitively exclude house 0? The answer to House Robber II is the maximum of these two linear subproblems.

This reduction works because the optimal solution either robs house 0 or it does not. If it robs house 0, then house n-1 must be excluded — we run House Robber I on indices 0 to n-2. If it does not rob house 0, then house n-1 is free to be robbed or not — we run House Robber I on indices 1 to n-1. One of these two cases contains the optimal answer.

Case 1 considers houses 0 through n-2 — the full array except the last house. By excluding house n-1 from the range, we guarantee that house 0 and house n-1 are never both available in the same subproblem. Running House Robber I on this range gives the best result when house n-1 is off-limits.

Case 2 considers houses 1 through n-1 — the full array except the first house. By excluding house 0, we similarly guarantee no circular conflict. Running House Robber I on this range gives the best result when house 0 is off-limits.

The final answer is max(case1, case2). Because the optimal solution to the circular problem must either avoid house 0 or avoid house n-1 (or both), one of the two cases will contain the optimal value. We never need a third case or a combined pass — the two linear subproblems are sufficient and exhaustive.

The argument is a clean case split. The optimal solution either includes house 0 or it does not. If it includes house 0, then house n-1 cannot be included (they are adjacent). So the optimal solution lives entirely within houses 0 to n-2 — exactly what case 1 computes. Case 1 returns the maximum possible value when house n-1 is excluded.

If the optimal solution does not include house 0, then the problem is unconstrained with respect to house n-1. The optimal solution lives within houses 1 to n-1 — exactly what case 2 computes. Case 2 returns the maximum possible value when house 0 is excluded. Since one of the two cases must describe the actual optimal solution, taking the max of both cases gives the correct answer.

No other cases exist. The circular constraint is binary: either house 0 is in the optimal solution or it is not. The two-pass approach exhausts both possibilities without overlap or gap. This reasoning pattern — case-split on the element that creates the circular dependency, solve each case linearly — generalizes to other circular DP problems.

Each linear pass is exactly the House Robber I recurrence over a contiguous subarray. The rolling-variable implementation uses two variables: prev2 tracks the best result two steps back, and prev1 tracks the best result one step back. At each index i, curr = max(prev1, prev2 + nums[i]). Then shift: prev2 = prev1, prev1 = curr. After iterating through all indices in the range, prev1 holds the answer for that pass.

The two-variable approach avoids allocating an O(n) dp array. Because each position only looks back two steps, there is no need to store earlier values. This is the standard O(1) space optimization for House Robber I, and it applies unchanged to each of the two linear passes in House Robber II.

The total time complexity is O(n) — two linear passes over at most n-1 elements each. The total space complexity is O(1) — only four variables are needed across both passes (prev2, prev1, curr for each pass, reused between passes). This is optimal: you must read all n inputs, and no additional memory is required beyond constant working variables.

Python: def rob(nums): n = len(nums); if n == 1: return nums[0]; def robLinear(start, end): prev2, prev1 = 0, 0; [prev2 := prev1, prev1 := max(prev1, prev2 + nums[i]) for i in range(start, end+1)]; return prev1. Cleaner without walrus: def robLinear(start, end): p2, p1 = 0, 0; for i in range(start, end+1): p2, p1 = p1, max(p1, p2+nums[i]); return p1. Main: return max(robLinear(0, n-2), robLinear(1, n-1)). Handles n==1 before calling robLinear to avoid empty ranges.

Java: public int rob(int[] nums) { int n = nums.length; if (n == 1) return nums[0]; return Math.max(robLinear(nums, 0, n-2), robLinear(nums, 1, n-1)); } private int robLinear(int[] nums, int start, int end) { int prev2 = 0, prev1 = 0; for (int i = start; i <= end; i++) { int curr = Math.max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = curr; } return prev1; }. The helper method is identical in structure to the standalone House Robber I solution.

The n==1 edge case must be handled before calling robLinear because robLinear(0, n-2) with n==1 becomes robLinear(0, -1), which is an empty range returning 0 — incorrect for a single house. Similarly robLinear(1, 0) is empty. Both cases return 0, but the correct answer for a single house is nums[0]. Always guard against n==1 before the two-pass logic.

House Robber I (LeetCode 198) is the direct predecessor and the subroutine used in House Robber II. The rolling-variable DP runs in O(n) time and O(1) space. Mastering House Robber I is a prerequisite for House Robber II — the two-pass reduction only works if you can implement House Robber I correctly and efficiently. House Robber III (LeetCode 337) extends the problem to a binary tree using post-order DP.

Min Cost Climbing Stairs (LeetCode 746) and Climbing Stairs (LeetCode 70) are the canonical introduction to 1D DP. Both use the same two-variable rolling technique: the current state depends only on the previous two states, so no array is needed. Once you are comfortable with these problems, House Robber I feels natural, and House Robber II is a single insight away.

The linear DP family — Climbing Stairs, Min Cost Climbing Stairs, House Robber, House Robber II, Jump Game, Maximum Subarray — all share the same structural template: define a simple recurrence over a 1D sequence, implement it with rolling variables for O(1) space, and handle edge cases at the boundaries. House Robber II adds the circular variant pattern, which appears in problems like Maximum Sum Circular Subarray (LeetCode 918) — a useful generalization to know.