Leetcode 213 : House Robber 2

Problem Statement

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.

Input

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 3:

Input: nums = [1,2,3]
Output: 3

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Approaches

Recursion - TLE

Since last element is the adjacent of the first element, we can have 3 observations.

1. In our answer, there will not be both first and last element together.
2. If we leave the first element, then its solving house robber 1 from index 1 to n.
3. If we leave the last element, then its solving house robber 1 from index 0 to n - 1.

So our final answer will be max(step2, step3).

But this recursive solution will gives TLE as there are so many overlapping subproblems

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
         if (length == 1) {
            return nums[0];
        }
        // the first option is do not consider the first element, but the last element
        // the second option is we consider first element, but not the last element.
        return Math.max(findMaxWealthNotTakingFirstOrLast(nums, 1, length - 1), findMaxWealthNotTakingFirstOrLast(nums, 0, length - 2));
    }

    private int findMaxWealthNotTakingFirstOrLast(int [] nums, int start, int end) {
        if (end < start) {
            return 0;
        }
        if (end == start) {
            return nums[start];
        }
        int pickThisElement = nums[end] + findMaxWealthNotTakingFirstOrLast(nums, start, end - 2);
        int notPickThisElement = findMaxWealthNotTakingFirstOrLast(nums, start, end - 1);
        return Math.max(pickThisElement, notPickThisElement);
    }
}

Recursion + Memoization

Use 2 dp tables. One to track the results while we are not considering the first element and the first one while we are considering the first element.

Then just apply the dp tables and save the result at the very end where we are doing the return statement.

TC : O(N)
SC : O(N) + O(N) + O(Stack Space)

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
         if (length == 1) {
            return nums[0];
        }
        int [] dp1 = new int [length];
        Arrays.fill(dp1, -1);
        // dp1 will be for the case where we do not consider the first element
        dp1[0] = nums[1];
        int [] dp2 = new int [length];
        Arrays.fill(dp2, -1);
        // dp2 will be for the case where we consider the first element
        dp2[0] = nums[0];
        // the first option is do not consider the first element, but the last element
        // the second option is we consider first element, but not the last element.
        return Math.max(findMaxWealthNotTakingFirstOrLast(nums, 1, length - 1, dp1), findMaxWealthNotTakingFirstOrLast(nums, 0, length - 2, dp2));
    }

    private int findMaxWealthNotTakingFirstOrLast(int [] nums, int start, int end, int [] dp) {
        if (end < start) {
            return 0;
        }
        if (end == start) {
            return nums[start];
        }
        if (dp[end] != -1) {
            return dp[end];
        }
        int pickThisElement = nums[end] + findMaxWealthNotTakingFirstOrLast(nums, start, end - 2, dp);
        int notPickThisElement = findMaxWealthNotTakingFirstOrLast(nums, start, end - 1, dp);
        return dp[end] = Math.max(pickThisElement, notPickThisElement);
    }
}

Tabulation

TC : O(N)
SC : O(N) + O(N) [Didn't considered the temp arraylist created]

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        ArrayList<Integer> arr1=new ArrayList<>();
        ArrayList<Integer> arr2=new ArrayList<>();

        // storing the elements to two separate list
        for(int i=0; i<length; i++){

            if(i != 0) arr1.add(nums[i]);
            if(i != length - 1) arr2.add(nums[i]);
        }
        int [] dp1 = new int [length];
        Arrays.fill(dp1, -1);
        int [] dp2 = new int [length];
        Arrays.fill(dp2, -1);
        return Math.max(maxResultLeavingNotLeavingFirstLast(arr1, dp1), 
                      maxResultLeavingNotLeavingFirstLast(arr2, dp2));
    }

    // just the house robber logic
    private int maxResultLeavingNotLeavingFirstLast(ArrayList<Integer> nums, int [] dp) {
        dp[0] = nums.get(0);
        for (int i = 1; i < nums.size(); i++) {
            int pickElement = nums.get(i);
            if (i > 1) {
                pickElement += dp[i - 2];
            }
            int notPickElement = dp[i - 1];
            dp[i] = Math.max(pickElement, notPickElement);
        }
        return dp[nums.size() - 1];
    }
}

Optimization using a single DP array

We already know the idea here is that since the last house and first house are adjacent, we have two options from the beginning.
Either start looting from the first house, thus skipping the last house.
Otherwise, start looting from the second house and consider the possibility of looting the last house as well.

TC : O(N)
SC : O(N)

The maximum from both these considerations would give us the maximum loot.

class Solution {
    int maxValue(int[] arr) {
        // code here
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int length = arr.length;
        if (length == 1) {
            return arr[0];
        }
        if (length == 2) {
            return Math.max(arr[1], arr[0]);
        }
        int considerFirstHouse = findMaxValue(arr, 0, length - 2);
        int notConsiderFirstHouse = findMaxValue(arr, 1, length - 1);
        return Math.max(considerFirstHouse, notConsiderFirstHouse);
    }

    private int findMaxValue(int [] arr, int start, int end) {
        int length = arr.length;
        int [] dp = new int [length];
        dp[start] = arr[start];
        dp[start + 1] = Math.max(arr[start], arr[start + 1]);
        for (int index = start + 2; index <= end; index++) {
            dp[index] = Math.max(dp[index - 1], arr[index] + dp[index - 2]);
        }
        return dp[end];
    }
}

Further optimization

We can make 1 more observation that, we only care about the previous house and the previous previous house. So instead of the dp arrays, we can just make use of two variable and apply the same logic which will reduce our space further

TC : O(N)
Sc : O(1)

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        return Math.max(maxResultLeavingNotLeavingFirstLast(nums, 1, length - 1), 
                      maxResultLeavingNotLeavingFirstLast(nums, 0, length - 2));
    }

    // just the house robber logic
    private int maxResultLeavingNotLeavingFirstLast(int [] nums, int start, int end) {
        int previous = nums[start];
        int previousPrevious = 0;
        for (int i = start + 1; i <= end; i++) {
            int pick = nums[i] + previousPrevious;
            int notPick = previous;
            int result = Math.max(pick, notPick);
            previousPrevious = previous;
            previous = result;
        }
        return previous;
    }
}