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, you would just apply the standard House Robber DP. But the circular constraint introduces a dependency between the first and last elements that a simple linear pass cannot handle. The key question becomes: how do we break the circular dependency so we can reuse the linear approach?

The crucial observation is this: since house 0 and house n-1 are adjacent, you can never rob both. That means the optimal solution either excludes house 0, or excludes house n-1 (or excludes both, which is covered by either case). So you can split the problem into two linear subproblems, solve each one, and take the maximum.

Key Constraints:

Intuition

The most straightforward way to think about this problem is to try every valid combination. At each house, you either rob it or skip it. The constraint is that you cannot rob two adjacent houses, and you cannot rob both the first and last house.

A natural starting point is recursion. Define a function that, given a range of houses, returns the maximum money you can get. At each house, make the take-or-skip decision:

To handle the circular constraint, run this recursive function twice: once for houses 0 through n-2 (excluding the last house), and once for houses 1 through n-1 (excluding the first house). The answer is the maximum of these two results.

Algorithm

Example Walkthrough

Input:

Case 1 (exclude last house): rob from [2, 3]. Try all combos: rob house 0 (2) or house 1 (3). Best = 3.

Case 2 (exclude first house): rob from [3, 2]. Try all combos: rob house 1 (3) or house 2 (2). Best = 3.

Code

The recursion recomputes the same subproblems over and over. What if we stored each result the first time we computed it?

Intuition

The brute force recursion is slow because it revisits the same states repeatedly. If we add a cache (memoization), we store the result for each subproblem and return it immediately on subsequent calls. This turns the exponential recursion into a linear-time algorithm.

The idea is identical to Approach 1: split the circular problem into two linear subproblems, then solve each with the take-or-skip recursion. The only difference is that we use a hash map or array to remember results we have already computed.

Algorithm

Example Walkthrough

Input:

The memoized recursion computes each subproblem exactly once. For Case 1 (houses 0-2): solve(2) calls solve(1) and solve(0), caches both. Result: 4. For Case 2 (houses 1-3): solve(3) calls solve(2) and solve(1), caches both. Result: 3.

Code

The recursion stack is unnecessary because the subproblems have a natural left-to-right order. Can we compute them iteratively instead?

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 at each step we only look at the previous two values. Can we replace the array with just two variables?

Intuition

Looking back at the DP recurrence, dp[i] = max(dp[i-1], nums[i] + dp[i-2]), we see that each state only depends on the previous two states. So instead of maintaining a full array, we can use just two variables: prev1 (the best from one house back) and prev2 (the best from two houses back). As we move forward, we update these in a rolling fashion.

This is the same optimization you would apply to the Fibonacci sequence: instead of storing all values, just keep track of the last two.

Algorithm

Example Walkthrough

Code