Problem
You are given an integer arraynums, where nums[i] represents the amount of money in the ith house.
The houses are arranged in a circle, which means the first and last houses are adjacent. You cannot rob two adjacent houses. Return the maximum amount of money you can rob.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [2,3,2]Output
3Solution
This problem can be solved using Memoization.The main difference from the original House Robber problem is that the houses are arranged in a circle. Therefore, the first and last houses are adjacent and cannot both be robbed.
To handle this, we divide the problem into two cases:
1. Exclude the last house: Consider houses from index
0 to n - 2.
2. Exclude the first house: Consider houses from index
1 to n - 1.
The
robHelper() method solves the standard House Robber problem for a given range. The parameter i represents the current house, while n represents the exclusive end of the range.
For each house, we have two choices:
Rob the current house: Add
nums[i] and move to i + 2, because adjacent houses cannot be robbed. Skip the current house: Move to
i + 1 and consider the next house.
We take the maximum of these two choices and store the result in
memo[i][n] to avoid recalculating the same state.
class Solution {
public int rob(int[] nums) {
int n = nums.length;
// With only one house, rob that house.
if (n == 1) {
return nums[0];
}
Integer[][] memo = new Integer[n][n + 1];
// Case 1: Exclude the last house.
// Consider houses from index 0 to n - 2.
int case1 = robHelper(nums, 0, n - 1, memo);
// Case 2: Exclude the first house.
// Consider houses from index 1 to n - 1.
int case2 = robHelper(nums, 1, n, memo);
// Choose the maximum amount from both cases.
return Math.max(case1, case2);
}
private int robHelper(int[] nums, int i, int n, Integer[][] memo) {
// Reached the end of the current range.
if (i >= n) {
return 0;
}
// Return the already calculated result.
if (memo[i][n] != null) {
return memo[i][n];
}
// Two choices:
// 1. Rob current house and skip the next house.
// 2. Skip current house and move to the next house.
return memo[i][n] = Math.max(
nums[i] + robHelper(nums, i + 2, n, memo),
robHelper(nums, i + 1, n, memo)
);
}
}
Complexity
Each house is processed at most once for each of the two cases. Therefore, the time complexity isO(n).
The memoization array and recursion stack require
O(n) space.
Tabulation Approach
We can also solve each of the two cases using bottom-up Dynamic Programming.For a linear range of houses,
dp[i] represents the maximum amount that can be robbed up to house i.
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])class Solution {
public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
return Math.max(
robRange(nums, 0, nums.length - 2),
robRange(nums, 1, nums.length - 1)
);
}
private int robRange(int[] nums, int start, int end) {
int length = end - start + 1;
if (length == 1) {
return nums[start];
}
int[] dp = new int[length];
dp[0] = nums[start];
dp[1] = Math.max(nums[start], nums[start + 1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(
dp[i - 1],
nums[start + i] + dp[i - 2]
);
}
return dp[length - 1];
}
}
Complexity
Both ranges are processed once, resulting inO(n) time complexity. The DP array requires O(n) extra space.
Space Optimized Approach
In the tabulation approach, each state depends only on the previous two states. Therefore, we can replace the DP array with two variables.We solve the same two cases, but calculate each one using
O(1) extra space.
class Solution {
public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
return Math.max(
robRange(nums, 0, nums.length - 2),
robRange(nums, 1, nums.length - 1)
);
}
private int robRange(int[] nums, int start, int end) {
int previousTwo = 0;
int previousOne = 0;
for (int i = start; i <= end; i++) {
int current = Math.max(
previousOne,
nums[i] + previousTwo
);
previousTwo = previousOne;
previousOne = current;
}
return previousOne;
}
}
Complexity
Each house is processed a constant number of times, resulting inO(n) time complexity. Only a constant number of variables are used, requiring O(1) extra space.