Data Structures & Algorithms in Java – Dynamic Programming – House Robber II

Problem:

A robber goes to rob in a series of houses built next to each other forming a circle. So the first house and last house are next to each other. The robber cannot steal from consecutive houses as it would trigger an alarm. Find the maximum money the robber can steal.

Input:

[2,3,2]

Each value in the array represents the money present in the house in that index position.

Output:

3

Because you cannot steal from first house and last house since they are adjacent to each other

For the input [1,2,3,1] the output is 4 since the robber can steal from house 1 and house 3 (1+3)

Try out the solution here:

https://leetcode.com/problems/house-robber-ii/

Solution:

Hint:

The solution is same as the previous House Robber problem:

The only difference is ,

Since first and last house are adjacent to each other, apply the above algorithm from house 1 to house n-1 separately and from house 2 to house n separately , where n is the total number of houses. Find the maximum of the two.

ALGORITHM:

STEP1: If the number of houses is 1 , return the money in that house

STEP2: Initialize two output arrays one for house 1 to house n-1 and another for house 2 to house n.

STEP3: Initialize the first value of the first array to the money in the first house and the first value of the second array to the money in the second house

STEP4: Initialize the second value of the first array to the maximum of the money in the first two houses and the second value of the second array to the maximum of the money in the second and third house.

STEP5: For the rest of the houses , find the maximum value of the previous maximum or the sum of the current money value and the previous to previous maximum . Store this in the respective arrays.

STEP6: Return the maximum of the last value in both the arrays.

Code:

class Solution {
    public int rob(int[] nums) {
        
        if(nums.length ==1){
            
            return nums[0];
        }
        
        int[] dp1 =new int[nums.length];
        
        int[] dp2 =new int[nums.length];
        
        
        dp1[0] = nums[0];
        
        if(nums.length > 1){
            
            dp1[1] = Math.max(nums[1], nums[0]);
            
            dp2[1] = nums[1];
            
            if(nums.length > 2){
                
                dp2[2] =Math.max(nums[1],nums[2]);
                
                
            }
        }
        
        //start from the third house for the first array
        for(int i =2;i<nums.length;i++){
            
            
            //dont include the last house
            if(i < nums.length -1){
            
            dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i]);
                
            }
            //start from the fourth house for the second array
            if(i > 2){
                
                dp2[i] = Math.max(dp2[i-1],dp2[i-2]+nums[i]);
            }
        }
        
  
        return dp1[dp1.length-2] > dp2[dp2.length-1] ? dp1[dp1.length-2] : dp2[dp2.length-1];
    }
}

The above code can be further refactored by starting the index position of the first output array from index 1 instead of 0 and from index 2 for the second array . This will reduce the lines of code :

class Solution {
    public int rob(int[] nums) {
        
        if(nums.length ==1){
            
            return nums[0];
        }
        
        int[] dp1 =new int[nums.length];
        
        int[] dp2 =new int[nums.length+1];
        
        
        dp1[1] = nums[0];
        

        for(int i =2;i<=nums.length;i++){
            
            
            
            if(i < nums.length ){
            
            dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i-1]);
                
            }
          dp2[i] = Math.max(dp2[i-1],dp2[i-2]+nums[i-1]);
     }
        
  
        return dp1[dp1.length-1] > dp2[dp2.length-1] ? dp1[dp1.length-1] : dp2[dp2.length-1];
    }
}

The time complexity is O(n) since we make a single iteration through the array.

Space complexity is O(2n) since we use two output arrays.

The above solution was the fastest in leetcode as the time of this writing:

That’s it!