House Robber II — Circular Array DP
Sanjeev SharmaAdvertisement
Problem
Houses in a circle. Can't rob adjacent. Maximize.
Approach — Two Linear Passes
Since first and last can't both be robbed, run House Robber on nums[0:-1] and nums[1:], return max.
Time: O(n) | Space: O(1)
Solutions
Python
class Solution:
def rob(self, nums: list[int]) -> int:
def rob_linear(arr):
prev2=prev1=0
for n in arr: prev2,prev1=prev1,max(prev1,prev2+n)
return prev1
if len(nums)==1: return nums[0]
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
C++
class Solution {
int robLinear(vector<int>& nums, int lo, int hi){
int prev2=0,prev1=0;
for(int i=lo;i<=hi;i++){int c=max(prev1,prev2+nums[i]);prev2=prev1;prev1=c;}
return prev1;
}
public:
int rob(vector<int>& nums){
int n=nums.size();
if(n==1) return nums[0];
return max(robLinear(nums,0,n-2),robLinear(nums,1,n-1));
}
};
Java
class Solution {
private int robLinear(int[] nums, int lo, int hi){
int prev2=0,prev1=0;
for(int i=lo;i<=hi;i++){int c=Math.max(prev1,prev2+nums[i]);prev2=prev1;prev1=c;}
return prev1;
}
public int rob(int[] nums){
int n=nums.length;
if(n==1) return nums[0];
return Math.max(robLinear(nums,0,n-2),robLinear(nums,1,n-1));
}
}
Complexity
- Time: O(n) | Space: O(1)
Advertisement
