Problem 25 - House Robber II

Explore our archive for previous posts.

Question

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

Constraints:

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 1000

Approach

This problem is an extension to the House Robber problem discussed in

the previous edition. Please check out the solution to that problem first before proceeding with understanding this problem.

To extend the previous solution of the “House Robber” problem to this problem, we need to consider the circular nature of the house arrangement. In this modified problem, the houses form a circular street, meaning the first and last houses are adjacent.

To solve this problem, we can break it down into two separate cases:

1. Rob the first house and don't rob the last house.

2. Don't rob the first house and rob the last house.

We can apply the same dynamic programming approach used in the previous solution to both of these cases and then take the maximum of the two results.

This extended solution uses a helper method robRange to handle the dynamic programming approach for a given range of houses. We first handle the case of robbing the first house and not robbing the last house, then the case of not robbing the first house and robbing the last house. Finally, we return the maximum amount from these two cases.

Solution

Solve it here

class Solution {
    public int rob(int[] nums) {
        // Only one house, so we can only rob that house
        if (nums.length == 1) {
            return nums[0]; 
        }
        
        // Rob the first house, don't rob the last house
        int max1 = robRange(nums, 0, nums.length - 2); 

        // Don't rob the first house, rob the last house
        int max2 = robRange(nums, 1, nums.length - 1); 
        
        // Take the maximum of the two cases
        return Math.max(max1, max2); 
    }
    
    private int robRange(int[] nums, int start, int end) {
        int prevMax = 0;
        int currMax = 0;
        
        for (int i = start; i <= end; i++) {
            int temp = currMax;
            currMax = Math.max(prevMax + nums[i], currMax);
            prevMax = temp;
        }
        
        return currMax;
    }
}

Time and space complexity

Time Complexity: The time complexity of the solution is O(n), where 'n' is the length of the input array nums. The algorithm iterates through the array once, performing constant-time operations at each step.

Space Complexity: The space complexity is O(1) as the solution uses only a constant amount of additional space. It maintains a few variables (max1, max2, prevMax, and currMax) to store the maximum amounts, regardless of the input size.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!