House Robber II
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
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 1000
Dynamic Programming
Approach
Since the houses are in a circle, we cannot rob both the first and the last house. This means we have two scenarios to consider: 1. We rob houses from index 0 to n-2 (skipping the last house). 2. We rob houses from index 1 to n-1 (skipping the first house). The answer is the maximum of the results from these two scenarios, plus a base case for when there is only one house. We can reuse the logic from the standard "House Robber" problem as a helper function.
Complexity Analysis
Time complexity is O(n) as we traverse the array twice. Space complexity is O(1) in Java. In Python, slicing creates a copy taking O(n) space, but this can be optimized to O(1) by passing indices instead of slicing.
class Solution { public int rob(int[] nums) { if (nums.length == 1) return nums[0]; // Return the max of two scenarios: // 1. Skip the last house // 2. Skip the first house return Math.max( helper(nums, 0, nums.length - 2), helper(nums, 1, nums.length - 1) ); } private int helper(int[] nums, int start, int end) { int rob1 = 0; int rob2 = 0; for (int i = start; i <= end; i++) { int temp = Math.max(nums[i] + rob1, rob2); rob1 = rob2; rob2 = temp; } return rob2; }}