House Robber Interview Question

House Robber Interview Question

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.

 

Example 1:

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 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Approach :

First, we have to find a solution for the smallest example. If we rob either rob ith and i-2th house or else we can rob i-1th house, because we cannot rob adjacent houses. We can take num[i] + num[i-2] or else num[i-1]. Base cases of the problem are,

arr= [1],

nums[0] = > maxProfit


arr = [1,2]  largest of two element is the max

Math.max(nums[0],nums[1]) => maxProfit


arr = [1,2,3] , i = 3

Math.max( nums[2] + nums[0], nums[1])  => maxProfit


Likewise, for large input, we can follow a bottom-up approach. The bottom-up approach means we solve the sub-problems and combine the result of all the sub-problems to form an answer for the large problem. For example, we first solve for small inputs like i = 1,2,3 and combine that to solve i =4.

To achieve a bottom-up approach we are using dynamic programming. Dynamic Programming (DP) is an algorithmic technique in which small sub-problems are solved first and after that solution for the original problem is computed. We solve and store subproblem results in dp single dimensional array. Later we combine the solutions in the array to find the solution for the original problem. We find the maximum amount robbed till ‘i’ and store it in array dp[i].

Program:

class Solution {
    public int rob(int[] nums) {
        
        int len = nums.length;
        
        if(len == 1)
            return nums[0];
        
        int max =  Math.max(nums[0],nums[1]);
        
        if(len == 2)
        {
            return max;
        }
        
        //mem stores maximum amount robbed till that index
        int dp[] = new int[len];
        dp[0] = nums[0];
        dp[1] = max;   
        
        for(int i = 2; i<len; i++)
        {
         
            //max amount till i = (max amount till i-2+ amount at i) or (maximum amount till previous house)
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
      
        return dp[len-1];
        
    }
}

Analysis:

Time Complexity – O(n) since we traverse the input array once

Space Complexity – O(n) since we store the max profit in dp array with size same as the size of the input array.

You Might also like…

Sum of Nodes with Even-Valued Grandparent

Zoho Interview Question 2022 | Sorting

 

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
5 1 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x