DSAPrep
Medium1-D DP

House Robber II

You are a professional robber planning to rob houses along a street, except now all the houses are arranged in a circle -- the first house is the neighbor of the last one. Adjacent houses still have connected security systems.

Given an integer array nums representing the amount of money at each house, return the maximum amount you can rob tonight without alerting the police.

Example 1

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

Example 2

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

Example 3

Input: nums = [1,2,3]
Output: 3

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000
View original on LeetCode ↗

The only thing the circle changes is that house 0 and house n-1 can no longer both be robbed. So any valid plan either excludes house 0 or excludes house n-1 (or both) – it can never need both restrictions at once, so checking those two cases separately and taking the max covers every possibility. Each case is then a plain non-circular House Robber on a slice of the array.

Brute Force Recursion

Time O(2ⁿ)Space O(n)

Reuse the linear House Robber recursion on two slices: houses 0..n-2 (excluding the last house) and houses 1..n-1 (excluding the first house). The better of the two is the answer.

class Solution:
    def rob(self, nums: list[int]) -> int:
        def robLine(houses: list[int]) -> int:
            def helper(i: int) -> int:
                if i < 0:
                    return 0
                return max(helper(i - 1), helper(i - 2) + houses[i])
            return helper(len(houses) - 1)


        n = len(nums)
        if n == 1:
            return nums[0]
        return max(robLine(nums[:-1]), robLine(nums[1:]))

Each robLine call is the exponential House Robber recursion, run twice → still O(2ⁿ) time, O(n) recursion depth.

Bottom-Up DP

OptimalTime O(n)Space O(n)

Run the linear House Robber DP on nums[0:n-1] and on nums[1:n], and take the larger result. Each linear pass fills dp[i] = max(dp[i-1], dp[i-2] + houses[i]) left to right.

class Solution:
    def rob(self, nums: list[int]) -> int:
        def robLine(houses: list[int]) -> int:
            prev2, prev1 = 0, 0
            for money in houses:
                prev2, prev1 = prev1, max(prev1, prev2 + money)
            return prev1


        n = len(nums)
        if n == 1:
            return nums[0]
        return max(robLine(nums[:-1]), robLine(nums[1:]))

Trace the winning pass for nums = [1, 2, 3, 1]: excluding the last house gives houses [1, 2, 3].

1
0
·
1
·
2
1 / 3
comparingresult

dp[0] = houses[0] = 1. Only one house available, rob it.

This pass (excluding house index 3) yields 4. Excluding house index 0 instead gives houses [2, 3, 1], whose best is 3. max(4, 3) = 4, matching the expected answer.

Each linear pass is O(n) time, O(1) space with rolling variables (shown here as a small full array for clarity); running it twice keeps the overall complexity at O(n) time, O(1) space.