House Robber Leetcode Solution

Difficulty Level Easy
Frequently asked in Amazon Apple Cisco Microsoft Oracle
algorithms coding Dynamic Programming Interview interviewprep LeetCode LeetCodeSolutionsViews 10104

Problem Statement

In this problem there are houses in a street and House robber has to rob these houses. But the problem is that he can’t rob more than one house successively i.e which are adjacent to each other. Given a list of non-negative integers representing the amount of money of each house, we have to find out the maximum amount of money he can get.

Example

nums = [1,2,3,1]
4

Explanation:House Robber

Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

nums = [2,7,9,3,1]
12

Explanation:

Rob house 1 (money = 2), rob house 3 (money = 9) and then 5th (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Approach

This problem can not be solved by greedy approach.
Let us take an example:
nums = [1,7,9,5,1,3,4]

If we would go for max element in the array(ie. 9), we would loose its adjacent sum (ie. 7+5). And best we can have is 15 as total sum.

If we go for even or odd position elements we have even sum=15 (7+5+3) and odd sum=15(1+9+1+4).

The optimum answer for this example will be [7+5+4]=12.

Hence to solve this type of problem we have to search for all choices recursively and pick out the maximum from them. Let us denote that:

f(n) = Largest amount that you can rob from first house to nth indexed house.
Ai = Amount of money at the ith index house.

At each house we have the choice of robbing it or leaving it.
case 1 – if we pick last house:
then, we cant pick (n-1)th house, hence f(n)= An + f(n-2)
case 2 – if we leave last house:
then, we will stick with the max profit till (n-1)th house, hence f(n)= f(n-1)

Let us see base cases.
n = 0, clearly f(0) = A0.
n = 1, then f(1) = max(A0, A1).

Hence we can summarize the formula as following :
f(n)= max( An + f(n-2) , f(n-1) )

This is a recursive formula which we can implement through simple recursion but here the time complexity will be O(2^n). Therefore we will use dynamic programming approach and store the intermediate results in an array.
After calculating we will return the value stored at nth(last) index in array.

Implementation

C++ Program for House Robber Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

int rob(vector<int>& nums)
{
    int n=nums.size();

    if(n==0) return 0;
    if(n==1) return nums[0];

    int a[n];

    a[0]=nums[0];
    a[1]=max(nums[0],nums[1]);

    for(int i=2;i<n;i++)
    a[i]=max(nums[i]+a[i-2], a[i-1]);

    return a[n-1];

}
int main() 
{
    vector<int> arr={1,2,3,1};
    
    cout<<rob(arr)<<endl;
    
  return 0; 
}
4

Java Program for House Robber Leetcode Solution

import java.util.*;
import java.lang.*;

class HouseRobber
{  
    public static int rob(int[] nums) {
        
        int n=nums.length;
        
        if(n==0) return 0;
        if(n==1) return nums[0];
        
        int a[]=new int[n];
       
        a[0]=nums[0];
        a[1]=Math.max(nums[0],nums[1]);
        
        for(int i=2;i<n;i++)
            a[i]=Math.max(nums[i]+a[i-2], a[i-1]);
        
        return a[n-1];
    }
    
    
    public static void main(String args[])
    {
        int arr[]={1,2,3,1};
        System.out.println(rob(arr));
    }
}
4

Complexity Analysis for House Robber Leetcode Solution

Time Complexity

O(n) : we are iterating from 1st house to nth house in a single loop, where n is the number of total houses.

Space Complexity 

O(n) : we have used an array of size n to store the intermediate result.

Translate »