You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

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.

Examples

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent.

Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 3:

Input: nums = [1,2,3]
Output: 3
Explanation: Rob house 2 (money = 2) or house 3 (money = 3).

Constraints

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

Thinking Process

  1. Circular Constraint: First and last houses are adjacent, so we can’t rob both
    • Exclude last house: [0..N-2]
    • Exclude first house: [1..N-1]
  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.
1D DP recurrence dp[i] 0 1 2 ? dp[i] from smaller indices / subproblems

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Solution

class Solution:
/
Cycle: rtn max(robLinear(0.. N - 2), robLinear(1,.. N - 1))
dp[i] = max(dp[i-2] + nums[i], dp[i - 1])
/
def rob(self, nums):
    N = len(nums)
    if(N == 1) return nums[0]
    return max(
    rob(nums, 0, N - 2),
    rob(nums, 1, N - 1)
    )
def rob(self, nums, l, r):
    prev2 = 0, prev1 = 0
    for(i = l i <= r i += 1) :
    curr = max(prev2 + nums[i], prev1)
    prev2 = prev1
    prev1 = curr
return prev1

Solution Explanation

Approach: 1D DP (this problem)

Key idea: 1. Circular Constraint: First and last houses are adjacent, so we can’t rob both

How the code works:

  1. Circular Constraint: First and last houses are adjacent, so we can’t rob both
    • Exclude last house: [0..N-2]
    • Exclude first house: [1..N-1]
    • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
    • Recurrence: how does the answer build from smaller indices?
    • Base cases first; optimize space if only prior row/layer is needed.

Walkthrough — input nums = [2,3,2], expected output 3:

You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent.

Common Mistakes

  1. Single house: nums = [5] → return 5
  2. Two houses: nums = [2,3] → return max(2,3) = 3
  3. Three houses: nums = [2,3,2] → return 3 (can’t rob first and last)
  4. All same: nums = [1,1,1,1] → return 2 (rob two non-adjacent)

  5. First and last are large: nums = [10,1,1,10] → return 10 (rob either first or last)

  6. Not handling single house: Forgetting edge case N == 1
  7. Wrong range: Using [0..N-1] and [1..N] instead of [0..N-2] and [1..N-1]
  8. Including both endpoints: Trying to include both first and last in one case
  9. Not taking maximum: Forgetting to compare both cases
  10. Index out of bounds: Not checking bounds when N == 1 or N == 2

Why This Works

Circular Constraint:

Since houses are arranged in a circle, if we rob house 0, we cannot rob house N-1. This creates two mutually exclusive cases:

  1. Case 1: Rob houses [0..N-2]
    • We can rob house 0, but not house N-1
    • This is a linear problem
  2. Case 2: Rob houses [1..N-1]
    • We cannot rob house 0, but can rob house N-1
    • This is also a linear problem

By taking the maximum of both cases, we ensure we get the optimal solution while respecting the circular constraint.

Visual Representation:

Case 1: [0..N-2] (exclude last)
  [0] [1] [2] ... [N-2] [N-1]
   ✓   ?   ?   ...   ?    ✗

Case 2: [1..N-1] (exclude first)
  [0] [1] [2] ... [N-2] [N-1]
   ✗   ?   ?   ...   ?    ✓

Result: max(case1, case2)

This problem extends House Robber to a circular arrangement. The key insight is breaking the circular constraint into two linear subproblems and taking the maximum, effectively reducing a circular problem to two linear problems.

Key Takeaways

  1. Circular Constraint: First and last houses are adjacent, so we can’t rob both
  2. Break into Two Cases:
    • Exclude last house: [0..N-2]
    • Exclude first house: [1..N-1]
  3. Reuse Linear Solution: Use the same DP logic from House Robber
  4. Space Optimization: O(1) space using two variables instead of array
  5. Edge Case: Single house doesn’t need splitting

References

Template Reference