DSA
House Robber - II
Covers: Recursive, Memoized version, Tabulation version. Optimal — Time O(n), Space O(1).
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.
Practice Link
Recursive#
The circular constraint means house 0 and house n-1 are adjacent, so we can never rob both. We break the problem into two independent linear sub-problems: rob houses [1, n-1] (exclude first) or rob houses [0, n-2] (exclude last), and take the maximum. Each sub-problem is solved with the same pick/skip recursion as House Robber I, but runs twice with different index ranges. Without caching the recursion is exponential.
class Solution {
public:
int robHouses(vector<int> &nums, int start, int end)
{
if(start>end)
return 0;
int take = nums[end] + robHouses(nums, start, end-2);
int notTake = robHouses(nums, start, end-1);
return max(take, notTake);
}
int rob(vector<int>& nums) {
return max(robHouses(nums, 1, nums.size()-1), robHouses(nums, 0, nums.size()-2));
}
};
Time Complexity: O(2^n) --> TLE
Space Complexity: O(n)
Memoized version#
We run two separate memoized House Robber I calls — one on [1, n-1] and one on [0, n-2] — using independent memo arrays so states from different ranges don't collide. Each sub-problem is solved in O(n), giving O(n) overall time and O(n) space for the two memo arrays.
class Solution {
public:
int robHouses(vector<int> &nums, int start, int end, vector<int> &memo)
{
if(start>end)
return 0;
if(memo[end]!=-1)
return memo[end];
int take = nums[end] + robHouses(nums, start, end-2, memo);
int notTake = robHouses(nums,start, end-1, memo);
return memo[end] = max(take, notTake);
}
int rob(vector<int>& nums) {
if(nums.size()==1)
return nums[0];
vector<int> memo1(nums.size(),-1);
vector<int> memo2(nums.size(),-1);
return max(robHouses(nums, 1, nums.size()-1, memo1), robHouses(nums, 0, nums.size()-2, memo2));
}
};
Time Complexity: O(n)
Space Complexity: O(n)
Tabulation version#
Iteratively fill a dp array for each of the two linear sub-ranges [0, n-2] and [1, n-1]. The helper is the same bottom-up fill as House Robber I, parameterized by start and end. Running the helper twice and taking the max gives the answer in O(n) time and O(n) space, with no recursion stack.
class Solution {
public:
int robHouses(vector<int>& nums, int start, int end) {
int n = end-start+1;
if(n==0)
return 0;
if(n==1)
return nums[start];
vector<int> dp(n, 0);
dp[0] = nums[start];
dp[1] = max(nums[start], nums[start+1]);
for(int idx=2;idx<n;idx++)
{
dp[idx] = max(dp[idx-1], nums[start+idx] + dp[idx-2]);
}
return dp[n-1];
}
int rob(vector<int>& nums) {
int n= nums.size();
if(n==0)
return 0;
if(n==1)
return nums[0];
int case1 = robHouses(nums, 0, n-2);
int case2 = robHouses(nums, 1, n-1);
return max(case1, case2);
}
};
Time Complexity: O(n)
Space Complexity: O(n)
Space Optimized#
Replace the dp array in each sub-range with two rolling variables (prev1, prev2). Each linear pass over the sub-range runs in O(n) with O(1) extra space. Running it twice stays O(1) space overall.
class Solution {
public:
int robHouses(vector<int>& nums, int start, int end) {
int n = end-start+1;
if(n==0)
return 0;
if(n==1)
return nums[start];
int prev2 = nums[start];
int prev1 = max(nums[start], nums[start+1]);
int curr = prev1;
for(int idx=2;idx<n;idx++)
{
curr = max(prev1, nums[start+idx] + prev2);
prev2 = prev1;
prev1=curr;
}
return curr;
}
int rob(vector<int>& nums) {
int n= nums.size();
if(n==0)
return 0;
if(n==1)
return nums[0];
int case1 = robHouses(nums, 0, n-2);
int case2 = robHouses(nums, 1, n-1);
return max(case1, case2);
}
};
Time Complexity: O(n)
Space Complexity: O(1)