This is a direct extension of the classic House Robber problem, but with a twist: the houses are arranged in a circle instead of a straight line. That circular arrangement means the first and last houses are neighbors, so you cannot rob both of them.

If the houses were in a line, the standard House Robber DP would apply directly. The circular constraint adds a dependency between the first and last elements that a single linear pass cannot handle. To reuse the linear approach, we need to break that circular dependency.

Since house 0 and house n-1 are adjacent, they can never both be robbed. The optimal solution therefore excludes house 0, excludes house n-1, or excludes both. The "both excluded" case is already contained in each of the first two, so two scenarios suffice: split the problem into two linear subproblems, solve each, and take the maximum.

Key Constraints:

Intuition

Try every valid combination. At each house, either rob it or skip it, subject to two rules: no two adjacent houses, and not both the first and last house.

Recursion expresses this directly. A function takes a range of houses and returns the maximum money obtainable from it. At each house it makes the take-or-skip decision:

The circular constraint is handled by running this recursion twice: once over houses 0 through n-2 (excluding the last house), and once over houses 1 through n-1 (excluding the first house). The answer is the maximum of the two results.

Algorithm

Example Walkthrough

Input:

Case 1 (exclude last house): solve on houses 0 through 1. robLinear(0, 1) compares skipping house 1 (which gives robLinear(0, 0) = 2) against taking house 1 (nums[1] + robLinear(0, -1) = 3 + 0 = 3). The max is 3.

Case 2 (exclude first house): solve on houses 1 through 2. robLinear(1, 2) compares skipping house 2 (robLinear(1, 1) = 3) against taking house 2 (nums[2] + robLinear(1, 0) = 2 + 0 = 2). The max is 3.

The final answer is max(3, 3) = 3.

Code

The same subproblems are recomputed across the recursion tree. Caching each result the first time it is computed removes that redundant work.

Intuition

The brute force recursion is slow because it revisits the same states repeatedly. A cache (memoization) stores the result for each subproblem and returns it on later calls, turning the exponential recursion into a linear-time algorithm.

The logic is identical to Approach 1: split the circular problem into two linear subproblems, then solve each with the take-or-skip recursion. The difference is a cache that remembers results already computed. The cache is keyed by the end index, which is enough because start is fixed within a single call, so each subproblem is uniquely identified by where it ends.

Algorithm

Example Walkthrough

Input:

The memoized recursion computes each subproblem once and caches it by end.

Case 1 (houses 0 through 2): robMemo(end=2) needs robMemo(end=1) and robMemo(end=0). The base case gives end=0 -> nums[0] = 1. Then end=1 -> max(1, nums[1]+0) = max(1, 2) = 2, cached. Then end=2 -> max(2, nums[2]+1) = max(2, 4) = 4, cached. Result: 4.

Case 2 (houses 1 through 3): end=1 -> nums[1] = 2. end=2 -> max(2, nums[2]+0) = max(2, 3) = 3, cached. end=3 -> max(3, nums[3]+2) = max(3, 3) = 3, cached. Result: 3.

The final answer is max(4, 3) = 4.

Code

The subproblems have a left-to-right order, so they can be filled iteratively from the smallest index upward, removing the recursion stack entirely.

Intuition

Instead of solving subproblems top-down with recursion, we can solve them bottom-up by iterating from the first house to the last. At each house i, we compute the maximum amount we can rob from all houses up to i. The recurrence is the same: either rob house i and add the best from i - 2, or skip house i and carry forward the best from i - 1.

We still handle the circular constraint by running this DP twice: once on nums[0..n-2] and once on nums[1..n-1].

Algorithm

Example Walkthrough

Code

The DP array uses O(n) space, but each step reads only the previous two values. Those two values can be held in two variables, dropping the space to O(1).

Intuition

In the DP recurrence dp[i] = max(dp[i-1], nums[i] + dp[i-2]), each state depends on only the previous two states. Instead of a full array, two variables suffice: prev1 (the best from one house back) and prev2 (the best from two houses back), updated in a rolling fashion as the loop advances.

This is the same optimization used for the Fibonacci sequence, where keeping the last two values replaces storing the whole array.

Algorithm

Example Walkthrough

Code