House Robber

Problem Statement

LeetCode-198: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems 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.

Approach

The problem can be solved using dynamic programming. We can maintain an array loot of size n where loot[i] represents the maximum amount of money that can be robbed till the $i^{th}$ house. As the robber cannot rob two adjacent houses, the robber can either rob the $i^{th}$ house or the $(i-1)^{th}$ house.

We can represent the recursive relation as follows: $ loot[i] = max(loot[i-1],\ loot[i-2] + nums[i])$

• loot[i-1] represents the maximum amount of money that can be robbed till the $(i-1)^{th}$ house. In this case, current house at index $i$ is NOT robbed.
• loot[i-2] + nums[i] represents the case where current house at index $i$ is robbed. This will also include the maximum amount of money that can be robbed till the $(i-2)^{th}$ house.

Implementation

A java implementation of the approach is as follows:

public int rob(int[] nums) {
    if(nums.length < 2){
        return nums[0];
    }

    int[] loot = new int[nums.length+1];
    
    loot[0] = nums[0];
    // handle the case when there are only 2 houses
    loot[1] = Math.max(nums[0], nums[1]);
    
    for(int i=2; i < nums.length; i++){
        loot[i] = Math.max(loot[i-1], nums[i] + loot[i-2]);
    }
    
    return loot[nums.length-1];
}

We can further optimize the space complexity of the above implementation by using two variables to store the maximum amount of money that can be robbed till the $(i-1)^{th}$ house and $(i-2)^{th}$ house.

public int rob(int[] nums) {
    if(nums.length < 2){
        return nums[0];
    }
    
    int lootFromFirstHouse = nums[0];
    // handle only two inputs
    int lootFromSecondHouse = Math.max(nums[0], nums[1]);

    for(int i=2; i < nums.length; i++){
        int temp = lootFromSecondHouse;
        lootFromSecondHouse = Math.max(lootFromSecondHouse, nums[i] + lootFromFirstHouse);
        lootFromFirstHouse = temp;
    }
    return lootFromSecondHouse;
}

Complexity Analysis

• The time complexity for the above approach is $O(n)$ where $n$ is the number of houses.
• The space complexity for the first approach is $O(n)$. The space complexity for the optimized approach is $O(1)$.

Follow-up

LeetCode-213: is a follow-up problem where the houses are arranged in a circle. The first and last houses are adjacent. The robber cannot rob two adjacent houses.

To solve this problem, we can divide the problem into two sub-problems:

1. Rob the houses from $0$ to $n-2$.
2. Rob the houses from $1$ to $n-1$.
3. Return the maximum of the two sub problems.

public int rob(int[] nums) {
    if(nums.length < 2){
        return nums[0];
    } else if(nums.length < 3){
        return Math.max(nums[0], nums[1]);
    }
    return Math.max(rob(nums, 0 , nums.length-2), rob(nums, 1, nums.length-1));
}

public int rob(int[] nums, int start, int end) {
    if(nums.length < 2){
        return nums[start];
    }
    
    int lootFromFirstHouse = nums[start];
    // handle only two inputs
    int lootFromSecondHouse = Math.max(nums[start], nums[start+1]);

    for(int i=start+2; i <= end; i++){
        int temp = lootFromSecondHouse;
        lootFromSecondHouse = Math.max(lootFromSecondHouse, nums[i] + lootFromFirstHouse);
        lootFromFirstHouse = temp;
    }
    return lootFromSecondHouse;
}