House Robber

In this approach, we will compute all possible combinations with conditions given in the problem, that is if we rob house at i, then we have to skip the adjascent indexed house i+1.

• We will create a function bruteForceApproach that takes nums array as input argument.
• Create another helper function bruteForceApproachRec that take nums and start variable to indicate the start index of the sub array we should be considering.
  • Call this function recursively, by moving start to +2 index considering you want to rob current house and +1 index considering you dont want to rob the current house, and take the maximum out of these two possibilities.
  • Base case will be, when it reaches end of array or goes out of bounds as we are trying with +1 and +2 index from every start index, we simply return 0.
  

public class HouseRobber {

    static int bruteForceApproach(int[] nums) {
        return bruteForceApproachRec(nums, 0);
    }

    static int bruteForceApproachRec(int[] nums, int start) {
        if(start>=nums.length) {
            return 0;
        }
        return Math.max(nums[start] + bruteForceApproachRec(nums, start+2), bruteForceApproachRec(nums, start+1));
    }
}

Complexity Analysis:

Time complexity: Above code runs in O(2ⁿ) time where n is the length of nums input array, this is because we are creating a decision tree with two possibilities at each step.
Space complexity: O(n) as we are making recursive loops n times and this is the memory used by stack.

From the above brute force approach, we can notice that there are some overlapping problems.

If we look at the decision tree diagram from above brute force aproach, highlighted sub problems are overlapping.

• If we look at the decision tree diagram from above brute force aproach, highlighted sub problems are overlapping.
• So, in this approach, we will be caching sub problem result into a HashMap with start index as key and its result as value. When a sub problem is repeated and found in cache, we will return it, otherwise we will call the function recursively and cache its result.

import java.util.HashMap;

public class HouseRobber {

    static int dpMemoizationApproach(int[] nums) {
        HashMap<Integer, Integer> cache = new HashMap<>();
        return dpMemoizationApproachRec(nums, 0, cache);
    }

    static int dpMemoizationApproachRec(int[] nums, int start, HashMap<Integer, Integer> cache) {
        if(start>=nums.length) {
            return 0;
        }
        if(cache.containsKey(start)) {
            return cache.get(start);
        }
        int result = Math.max(nums[start] + bruteForceApproachRec(nums, start+2), bruteForceApproachRec(nums, start+1));
        cache.put(start, result);
        return result;
    }

}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums input array.
Space complexity: O(n) for the cache we are maintaining and stack for recursive calls.

In this approach we will look at solving the problem using Dynamic programming using tabulation caching mechanism.
The time and memory complexity will be same as above solution using memoization, but we can notice a pattern to improve memory complexity to constant in later solution.

Intution behind this solution is, when we are at ith indexed house, we will calculate the maximum amount that can be robbed at this index and cache that into dp temporary array. We gonna compute maximum amount that you can rob using below logic.

Max(nums[i] + dp[i-2], dp[i-1])

Base cases for this solution will be

• dp[0] = nums[0], because at 0^th index, maximum amount you can rob is just that house.
• dp[1] = Max(nums[0], nums[1]), because at 0^th indexed house has higher amount, you can rob that house and skip index 1 house or rob index 1 house and skip index 0 house.

Finally, take the last element from dp array, that will store the maximum amount that you can rob with the given conditions. Lets look at an example with nums array as [1, 2, 3, 1].

• In the first step, if the input array nums length is 1, just return the first element.
• In the first step, we will be initializing dp array with same length as nums input array.
• Then, update dp array with base cases. i.e. dp[0] = nums[0] and dp[1] = Max(nums[0], nums[1]), so the dp array looks like this after applying base cases. dp = [1, 2, 0, 0].
• For the next index i=2, maximum amount you can rob at this index will be Max(nums[2] + dp[0], dp[1]) so the dp array now will be dp = [1, 2, 4, 0]
• For the next index i=3, maximum amount you can rob at this index will be Max(nums[3] + dp[1], dp[2]) so the dp array now will be dp = [1, 2, 4, 4 ]
• As you see, maximum amount is stored at last index, we can simply return that dp[dp.length-1].

public class HouseRobber {

    static int dpTabulationApproach(int[] nums) {
        if(nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i=2; i<nums.length; i++) {
            dp[i] = Math.max(nums[i]+dp[i-2] , dp[i-1]);
        }
       return Math.max(dp[dp.length-1], dp[dp.length-2]);
    }
}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums input array.
Space complexity: O(n) since we have a dp array with size n.

If we look at above DP solution using tabulation, when calculating maximum amount you can rob at index i, we just need previous two values, that is maximum amount you can rob at i-2 and i-1.

• In this approach, we will create two variables m1 and m2 to hold previous values for i-2^nd step and i-1^st indexed houses.
• We will initialize m1 = 0 and m1 = 0.
• Next, for each index i compute the maximum that can be robbed using Max(nums[i]+m1, m2), store this into a temporary variable, then make this value as new m2 and current m2 to m1 for next iteration.

public class HouseRobber {

    static int dpMemoryOptimized(int[] nums) {

        int m1= 0;
        int m2 = 0;

        for(int i=0; i<nums.length; i++) {
            int temp = Math.max(nums[i]+m1 , m2);
            m1 = m2;
            m2 = temp;
        }
        return m2;
    }

}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums input array.
Space complexity: O(1) since we are only using m1, m2 and a temp variables.