Solution: House Robber II

Let's solve the House Robber II problem using the Dynamic Programming pattern.

We'll cover the following

Statement

A professional robber plans to rob some houses along a street. These houses are arranged in a circle, which means that the first and the last house are neighbors. The robber cannot rob adjacent houses because they have security alarms installed.

Following the constraints mentioned above and given an integer array money representing the amount of money in each house, return the maximum amount the robber can steal without alerting the police.

Constraints:

  • 1≤1\leq money.length ≤103\leq 10^3
  • 0≤0\leq money[i] ≤103\leq 10^3

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

Naive approach

The rule to decide about robbing a particular house is to either rob the current house and skip the adjacent house or skip the current house and rob the adjacent house. The house containing the greater amount will get selected from these two options. For the given set of houses, we must accumulate the robbed amount for all houses according to the rule mentioned above. This requires exhaustive testing of all possible combinations and selecting a combination that gives the maximum robbery amount.

We will have repeated subcombinations to traverse in multiple computations. Also, while robbing, we cannot allow the first and last houses to be robbed in a single combination because they are neighbors. So, we will divide the houses into two sets, ranging from 11 to n−1n−1 and 22 to nn, respectively. The maximum possible robbery amount will be computed for these sets separately, and the maximum of the two will be returned.

The time complexity for this approach would be O(2n)O(2^n), where nn is the size of the money array. This is because there are two possible options for each house. The space complexity will be O(n)O(n), which is the height of the recursion tree.

Optimized approach using dynamic programming

The optimized approach is to use the bottom-up approach. The bottom-up solution, also known as the tabulation method, is an iterative method of solving dynamic programming problems.

For each house, we can pick either that house or the two houses adjacent to it. The maximum of both will decide which is to be picked. We will store the maximum amount robbed for each house in a lookup array to be used in the later computations. As stated in the naive approach above, we will eliminate the possibility of selecting the first and last house simultaneously by dividing it into two sets.

Let’s try and implement the approach mentioned above:

  • We split the money array into two parts:
    • The first array will contain all the values except the last one, ranging from 00 to n−2n-2.
    • The second array will contain all the values except the first one, ranging from 11 to n−1n-1.

The steps mentioned below will be performed on both arrays, and the maximum of both will be the max amount robbed.

  • Initialize an array, lookupArray, which will store the maximum amount of money that can be robbed for houses ranging from 0 to the total number of houses.

  • If there is no house, the max amount robbed will be 0, stored in the lookup array at index 0.

  • If there is only one house, we pick that house.

  • If there is more than one house, we have two options for each house:

    • We can select the sum of the current house, i, and the already calculated amount for house, i – 2, from the lookup array.
    • We can select the amount for house i – 1 from the lookup array.

    The maximum of both values will be selected. Once all iterations are complete, we will return the value of the last index from the lookup array.

The slides below illustrate how we would like the algorithm to run:

Let’s take a look at the code for this solution below:

import java.util.Arrays;
class HouseRobber {
    public static int houseRobber(int[] money) {
        if (money == null || money.length == 0) {
            return 0;
        }
        if (money.length == 1) {
            return money[0];
        }
        return Math.max(houseRobberHelper(Arrays.copyOfRange(money, 0, money.length - 1)),
                houseRobberHelper(Arrays.copyOfRange(money, 1, money.length)));
    }
    private static int houseRobberHelper(int[] money) {
        int[] lookupArray = new int[money.length + 1];
        lookupArray[0] = 0;
        lookupArray[1] = money[0];
        for (int i = 2; i <= money.length; i++) {
            lookupArray[i] = Math.max(money[i - 1] + lookupArray[i - 2], lookupArray[i - 1]);
        }
        return lookupArray[money.length];
    }
    // Driver code
    public static void main(String[] args) {
        int[][] inputs = { { 2, 3, 2 }, { 1, 2, 3, 1 }, { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },
                { 7, 4, 1, 9, 3 }, {} };
        for (int i = 0; i < inputs.length; i++) {
            System.out.println((i + 1) + ".\tHouses: " + Arrays.toString(inputs[i]));
            System.out.println("\n\tMaximum loot: " + houseRobber(inputs[i]));
           System.out.println("-" + new String(new char[100]).replace('\0', '-') + "\n");
        }
    }
}
House Robber II

Time complexity

The time complexity of this solution is O(n)O(n), where nn is the length of money.

Space complexity

The space complexity of this solution is O(n)O(n), which is the space used by the lookup array.

Can we do better?

We can further improve this approach by using two variables instead of the lookup array. Since we are only using the previous two values, we can store them in variables and update them as we go along.

The time complexity will remain the same, O(n)O(n), because we still have to traverse over the money array. The space complexity, however, reduces to O(1)O(1) since we are only using two variables instead of a lookup array.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.