Last Updated: 6 Sep, 2022
House Robber
Moderate
Asked in companies
Mr. X. is a professional robber planning to rob houses along a street. Each house has a certain amount of money hidden.
Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two neighboring houses were broken into the same night.
You are given an array/list of non-negative integers 'A' representing the amount of money hidden at each house. Your task is to return the maximum amount of money Mr. X can rob tonight without alerting the police.
Example:
Input: [1,2,3,1]
Output: 4
Mr. X. can rob the first house and the third house, total money = 1 + 3.
Hence, the total money robbed by Mr. X. is 4.
Input Format :
The first line will contain the integer 'T', denoting the number of test cases.
The first line of each test case contains one integer 'N' denoting the size of array 'A'.
The second line of each test case contains 'N' single space-separated integers, elements of the array 'A'.
Output format :
For each test case, Return the maximum amount of money Mr. X can rob tonight without alerting the police.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= N <= 10^5
0 <= A[i] <= 10ٰ^9
Time Limit: 1 sec
Approaches
In this approach, we are trying out all possibilities.
At every 'i'th house robber has two options
- Rob the current house.
- Don't rob the current house.
If he is robbing the 'i'th house, he can have the money hidden at 'i'th house, and the money robbed till 'i-2'th house, let's say it 'X'.
If he is not robbing the 'i'th house, he can have the money robbed till 'i-1'th house, let's say it 'Y'.
So, the maximum money he robs till 'i'th house is max( X, Y ).
The steps are as follows:-
function houseRobberyHelper([int] A, int index):
- If all the houses are already covered, i.e., index >= A.size, return 0.
- Initialise an integer variable, 'X' to A[ index ] + houseRobberyHelper( A, index+2 ).
- Initialize an integer variable, 'Y' to houseRobberyHelper( A, index+1 ).
- Return the maximum of 'X and 'Y'.
function houseRobbery([int] A):
- Return houseRobberyHelper(A, 0).
We can see that we only need the answer to the 'i-1'th and 'i-2'th index to calculate the answer for the 'i'th index.
Hence, we can maintain two variables, 'lastAns' and 'secondLastAns', to store the answer till the 'i-1'th and the 'i-2'th index.
The answer for the current index can be the maximum of the 'secondLastAns' + 'A[i]' and 'lastAnswer'.
Before moving to the next index, 'secondLastAnswer' will be equal to 'lastAnswer', and 'lastAnswer' will be equal to 'curAnswer'.
Finally, return the answer on the 'N-1'th index. (0-based indexing).
The steps are as follows:-
function houseRobbery([int] A):
- If the size of array 'A' equals one, return 'A[0]' as the answer.
- Initialize the variables 'secondLastanswer' with 'A[0]', 'lastAnswer' with a maximum of 'A[0]' and 'A[1]' and 'curAnswer' with 'lastAnswer', respectively.
- Run a for loop form i=2 to N-1
- 'curAnswer' is the maximum of 'lastAnswer' and ( 'secondLastAnswer' + 'A[i]' ).
- 'secondLastAnswer' is equal to 'lastAnwser'.
- 'lastAnswer' is equal to 'curAnswer'.
- Return the value of'curAnswer'.