House Robber II
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 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
Input Format:
- An integer array nums representing the amount of money in each house
Output Format:
- Return the maximum amount of money you can rob 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 (circular arrangement). Instead, rob house 2 (money = 3).
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
Explanation:
Rob house 2 (money = 2) or rob house 3 (money = 3). We choose to rob house 3 for more money.
Solutions
Two-Pass Dynamic Programming
Break the circular arrangement by considering two scenarios: robbing houses 0 to n-2 (excluding the last house) or robbing houses 1 to n-1 (excluding the first house). Take the maximum result from these two scenarios.
Two-Pass DP Array Approach
Use dynamic programming arrays for both scenarios: excluding the first house and excluding the last house.
Algorithm Walkthrough
Example input: nums = [2,3,2]
Step-by-step execution:
- First scenario: Exclude the last house, consider nums = [2, 3]
- For nums = [2, 3]:
- prevMax = 2, currMax = max(2, 3) = 3
- Result for first scenario: 3
- Second scenario: Exclude the first house, consider nums = [3, 2]
- For nums = [3, 2]:
- prevMax = 3, currMax = max(3, 2) = 3
- Result for second scenario: 3
- Take the maximum of both scenarios: max(3, 3) = 3
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the process of breaking the circular arrangement into two linear subproblems and solving each with dynamic programming.
Key visualization elements:
- excluded house
- current house
- previous max profit
- current max profit
- decision made
Similar Questions
House Robber
MediumYou are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems 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.
Maximum Product Subarray
MediumGiven an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer. A subarray is a contiguous subsequence of the array.
Implementation Notes
This problem builds on the House Robber problem by adding a circular constraint. The key insight is to break the circle by considering two separate linear subproblems.