House Robber II | Leetcode 213

Welcome to the direct sequel to our House Robber guide! In House Robber II (Leetcode 213), the stakes are slightly higher. The robber has stumbled upon a neighborhood where the houses are arranged in a massive circle.

Problem Statement

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.

Example: nums = [2, 3, 2] => Output: 3 (You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses in a circle).

The Circular Street Dilemma

The ONLY difference between this problem and the original House Robber is that the array wraps around. Because the first house and the last house are connected, you can legitimately never rob both the first house and the last house.

This logic creates an incredibly elegant solution: We can simply reuse our exact same algorithm from the original House Robber problem, and run it two separate times:

1. Run it on the list of houses from 0 to N-2 (Skipping the last house completely).
2. Run it on the list of houses from 1 to N-1 (Skipping the first house completely).

Your final answer is simply the max() of those two runs!

graph TD
    A["nums = [1, 2, 3, 1]"] -->|"Skip Last"| B["Array 1: [1, 2, 3]"]
    A -->|"Skip First"| C["Array 2: [2, 3, 1]"]
    
    B -->|"Robbing Algorithm"| D("Max = 4")
    C -->|"Robbing Algorithm"| E("Max = 3")
    
    D --> F{"Return Max(4, 3)"}
    E --> F
    F --> G("Answer: 4")
    
    style F fill:#4CAF50,stroke:#fff,stroke-width:2px,color:#fff

Just like before, we will explore both the Top-Down Recursive (Memoized) approach and the absolutely optimal Bottom-Up O(1) Space approach.

Approach 1: Top-Down Recursion with Memoization

If we want to map this directly to a recursive tree, we can create a helper() function that accepts the start and end indices. We use a 2D cache (or simply slice the array) to memoize the recursive branches and avoid O(2^N) time limits.

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
            
        return max(self.helper(nums[:-1]), self.helper(nums[1:]))

    def helper(self, nums):
        memo = {}
        def dfs(i):
            if i < 0:
                return 0
            if i in memo:
                return memo[i]
                
            memo[i] = max(dfs(i - 2) + nums[i], dfs(i - 1))
            return memo[i]
            
        return dfs(len(nums) - 1)

Complexity Analysis

Approach 2: Optimal Bottom-Up DP (O(1) Space)

Of course, using a call stack natively uses O(N) space. To completely optimize this algorithm, we fall back to the pointer-swapping DP loop we built in House Robber.

We simply wrap that logic into a helper method, and execute it twice on our shifted boundaries!

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
            
        return max(self.rob_straight(nums[:-1]), self.rob_straight(nums[1:]))

    def rob_straight(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0
        for n in nums:
            temp = max(n + rob1, rob2)
            rob1 = rob2
            rob2 = temp
        return rob2

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (213)