House Robber II#

Difficulty: Medium

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.

Constraints:

  • 1 <= nums.length <= 100

  • 0 <= nums[i] <= 1000

Probelm Explanation:#

Certainly! The problem statement describes a scenario where you are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. However, there is a security system in place: adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses are broken into on the same night.

The twist in this problem is that the houses are arranged in a circle. That means the first house is the neighbor of the last one. So, robbing the first house has implications for the last house, and vice versa.

The goal is to find the maximum amount of money you can rob tonight without alerting the police. You need to implement a function that takes an integer array nums representing the amount of money in each house and returns the maximum amount of money that can be robbed without triggering the security system.

Here are a few examples to illustrate the problem:

  1. 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. The optimal strategy is to rob house 2 (money = 3).

  2. Example 2:

    Input: nums = [1, 2, 3, 1]
Output: 4
Explanation: Robbing house 1 (money = 1) and then robbing house 3 (money = 3) results in a total amount of 4. Robbing house 2 is skipped to avoid alerting the police.

  3. Example 3:

    Input: nums = [1, 2, 3]
Output: 3
Explanation: Since the houses are in a circle, you can choose either house 1, 2, or 3. The optimal strategy is to rob house 3 for a total amount of 3.

The constraints for the problem are that the length of the nums array is between 1 and 100, and the amount of money in each house (nums[i]) is between 0 and 1000.

Solution:#

Here’s a Python function to implement this algorithm:

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        def simple_rob(nums):
            # Helper function for basic house robbery problem
            prev, curr = 0, 0
            for num in nums:
                # Calculate the maximum amount of money that can be robbed
                # without alerting the police for each house
                prev, curr = curr, max(prev + num, curr)
            return curr

        # Check the base cases where the length of nums is 1 or 2
        if len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums[0], nums[1])

        # Case 1: First house is robbed, last house is not
        case1 = simple_rob(nums[:-1])

        # Case 2: First house is not robbed, last house is
        case2 = simple_rob(nums[1:])

        # Maximum of the two cases
        return max(case1, case2)

Explanation:#

The provided code defines a class Solution with a method rob, which aims to determine the maximum amount of money a professional robber can steal from houses arranged in a circle without alerting the police. Each house contains a certain amount of money, and adjacent houses have a security system that triggers if both are robbed on the same night.

The code uses dynamic programming to solve the problem efficiently. It contains a helper function simple_rob that computes the maximum amount of money that can be robbed from a linear arrangement of houses. The main method rob handles the circular arrangement by considering two cases: robbing the first house and not robbing the last, and not robbing the first house and robbing the last. The result is the maximum of these two cases.

The class is instantiated as solution, and the rob method is applied to three different scenarios (test cases) to demonstrate its functionality. The final output represents the maximum amount of money the robber can steal without triggering the security system.

Test cases:#

Here’s how you can use this solution:

# Example 1:

# Create an instance of the Solution class
solution = Solution()

nums1 = [2, 3, 2]
print(solution.rob(nums1))  # Output: 3

3

# Example 2:
nums2 = [1, 2, 3, 1]
print(solution.rob(nums2))  # Output: 4

4

# Example 2:
nums3 = [1, 2, 3]
print(solution.rob(nums3))  # Output: 3

3

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided code:

Time Complexity:#

The time complexity is primarily determined by the simple_rob helper function, which has a time complexity of O(N), where N is the number of houses in the input array. The main rob function calls simple_rob twice, once for the case of robbing the first house and not robbing the last, and once for the case of not robbing the first house and robbing the last. Therefore, the overall time complexity is O(N).

Space Complexity:#

The space complexity is O(1) because the space used by the algorithm is constant, regardless of the size of the input array. The only variables used are prev and curr in the simple_rob function, which represent the previous and current maximum amounts of money that can be robbed without alerting the police. These variables are updated iteratively, and no additional data structures are used that scale with the input size. Therefore, the space complexity is constant, or O(1).

In summary:

  • Time Complexity: O(N)

  • Space Complexity: O(1)

Challenging Exercises:#

  1. Optimization Challenge: Optimize the space complexity of the solution. Can you solve the problem with O(1) space complexity without sacrificing the time complexity?

  2. Circular Robbery Variations: Consider variations of the circular house robbery problem, such as allowing the robber to skip a certain number of houses or restricting the number of consecutive houses that can be robbed. Modify the solution to accommodate these variations.

Link to Problem: To see the House Robber II problem on LeetCode, click here!