Problem

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 houses.

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

This is an extension of House Robber

Similar Problem

House Robber House Robber 3 - Houses in Binary Tree House Robber 4

Solution

Method 1 - Naive

Since the houses are arranged in a circle, the first and last houses are adjacent, so they cannot both be robbed on the same night. This requires us to divide the problem into two subproblems:

  1. Rob houses from index 0 to n-2 (excluding the last house).
  2. Rob houses from index 1 to n-1 (excluding the first house).

The result will be the maximum of these two subproblems.

Naive Recursive Approach

To solve it naively and recursively:

  1. Define a helper function to determine the maximum sum that can be robbed from a linear segment of houses.
  2. Recursively decide whether to rob the current house or skip it.
  3. Compute the above two cases (excluding the last house and excluding the first house) and return the maximum.

Code

Java
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(robHelper(nums, 0, nums.length - 2), robHelper(nums, 1, nums.length - 1));
    }
    
    private int robHelper(int[] nums, int start, int end) {
        if (start > end) return 0;
        // Option 1: Rob current house
        int rob = nums[start] + robHelper(nums, start + 2, end);
        // Option 2: Skip current house
        int skip = robHelper(nums, start + 1, end);
        return Math.max(rob, skip);
    }
}
Python
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        def rob_helper(nums: List[int], start: int, end: int) -> int:
            if start > end:
                return 0
            # Rob current house or skip it
            rob = nums[start] + rob_helper(nums, start + 2, end)
            skip = rob_helper(nums, start + 1, end)
            return max(rob, skip)

        # Max between robbing from 0 to n-2 or 1 to n-1
        return max(rob_helper(nums, 0, len(nums) - 2), rob_helper(nums, 1, len(nums) - 1))

Complexity

  • ⏰ Time complexity: O(2^n). Divide into two subproblems (rob excluding the last house and rob excluding the first house), solved recursively. So, due to branching out, TC is O(2^n).
  • 🧺 Space complexity: O(n), due to the call stack.

Method 2 - Top Down DP with memoization

Memoization can optimise the naive recursion by avoiding repeated calculations for the same subproblems. Here’s how we’ll modify our approach:

  1. Use a helper function with start and end indices for a linear segment of the houses.
  2. Use a memoization table (array or dictionary) to store results of previously computed subproblems. Specifically, we memoise the result for each starting index to avoid redundant calculations.
  3. Compute the maximum result for the two cases (excluding the last house and excluding the first house).
  4. Return the maximum of the two results.

Code

Java
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(robHelper(nums, 0, nums.length - 2, new HashMap<>()),
                        robHelper(nums, 1, nums.length - 1, new HashMap<>()));
    }

    private int robHelper(int[] nums, int start, int end, HashMap<Integer, Integer> memo) {
        if (start > end) return 0;
        if (memo.containsKey(start)) return memo.get(start);
        
        // Option 1: Rob current house
        int rob = nums[start] + robHelper(nums, start + 2, end, memo);
        // Option 2: Skip current house
        int skip = robHelper(nums, start + 1, end, memo);
        
        int ans = Math.max(rob, skip);
        memo.put(start, ans);
        return ans;
    }
}
Python
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        def rob_helper(nums: List[int], start: int, end: int, memo: dict[int, int]) -> int:
            if start > end:
                return 0
            if start in memo:
                return memo[start]
            
            # Rob current house or skip it
            rob = nums[start] + rob_helper(nums, start + 2, end, memo)
            skip = rob_helper(nums, start + 1, end, memo)
            
            memo[start] = max(rob, skip)
            return memo[start]

        # Max between robbing from 0 to n-2 or 1 to n-1
        return max(rob_helper(nums, 0, len(nums) - 2, {}), rob_helper(nums, 1, len(nums) - 1, {}))

Complexity

  • ⏰ Time complexity: O(n). Each house (or subproblem) is computed only once, so the time complexity is O(n), where n is the number of houses.
    • Looking up and updating the memo table takes constant time for each house.
  • 🧺 Space complexity: O(n) for using memoisation table and recursion call stack in worst case.

Method 3 - Bottom up DP

The bottom-up approach eliminates recursion by iteratively solving the problem while keeping track of previous results. For the House Robber II problem, we’ll calculate the maximum amounts using two linear DP arrays—one excluding the last house and one excluding the first house.

  • Key Idea: Dynamically compute results for each house by maintaining the maximum money that can be robbed up to that house.

Steps For Bottom-Up Approach

  1. If there is only one house, return its value (nums[0]).

  2. Use the helper function twice for two subproblems:

    • One for robbing houses [0, n-2] (excluding the last house).
    • The other for robbing houses [1, n-1] (excluding the first house).

  3. In the helper function (for linear robbery problem):

    • Use two variables (prev1 and prev2) to store the maximum amount robbed up to the last two houses.
    • For each house, decide whether to rob it or skip it.

  4. Return the maximum of the two computed results.

Code

Java
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(robHelper(nums, 0, nums.length - 2), robHelper(nums, 1, nums.length - 1));
    }
    
    private int robHelper(int[] nums, int start, int end) {
        int prev1 = 0, prev2 = 0;
        for (int i = start; i <= end; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}
Python
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        def rob_helper(nums: List[int], start: int, end: int) -> int:
            prev1, prev2 = 0, 0
            for i in range(start, end + 1):
                curr = max(prev1, prev2 + nums[i])
                prev2 = prev1
                prev1 = curr
            return prev1

        # Max between robbing from 0 to n-2 or 1 to n-1
        return max(rob_helper(nums, 0, len(nums) - 2), rob_helper(nums, 1, len(nums) - 1))

Complexity

  • ⏰ Time complexity: O(n). Each house is visited once in both subproblems (excluding first or last house).
  • 🧺 Space complexity: O(1). Only two variables are used to store intermediate results.