House Robber

Moderate
0/80
Average time to solve is 26m
profile
Contributed by
73 upvotes
Asked in companies
CognizantTata Consultancy Services (TCS)Paytm (One97 Communications Limited)

Problem statement

A thief wants to loot houses. He knows the amount of money in each house. He cannot loot two consecutive houses. Find the maximum amount of money he can loot.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains a single integer 'N' denoting the total number of houses.

The second line of input contains 'N' single space-separated integers, denoting the amount of money in every 'i-th' house.
Output Format : 
The only line of output will print the maximum amount of loot that is possible.
Note : 
You don’t need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
0 <= 'N' <= 10^5
0 <= 'A[i]' <= 10^4

Where 'A[i]' represents the money present in the 'i-th' house.

Time limit: 1 sec
Sample Input 1:
4
10 2 3 11
Sample Output 1:
21
Explanation of Sample Input 1:
Since the thief cant loot two consecutive houses, the ways in which he may loot are:

1. [10, 3]: a total loot of 13
2. [10, 11]: a total loot of 21
3. [2, 11]: a total loot of 13
4. [10]: a total loot of 10
5. [2]: a total loot of 2
6. [3]: a total loot of 3
7. [11]: a total loot of 11

We can't neglect the option to loot just either of the houses if it yields the maximum loot.

From all the possible seven ways, the second option yields the maximum loot amount and hence the answer.
Sample Input 2:
6
5 5 10 100 10 5
Sample Output 2 :
110
Hint

Can you think of a brute force approach?

Approaches (3)
Recursive Approach

Suppose that the robber is at the ith house. The robber has two options:

  • If he decides to rob this house, then he cannot rob the next house, so he’ll have to go to the house after that.
  • If he decides not to rob this house, he has no restriction over choosing the next house.

You will follow the same for the rest of the houses. Thus, if maxLoot(i) is the maximum loot possible when we’re at the ith house, then the recursive definition follows:

maxLoot(i) = maximum( loot[i] + maxLoot(i+2), maxLoot(i+1))

 

Note: This approach has an exponential time complexity because this problem has overlapping subproblems for which we recompute the answer over and over again. To avoid that recomputation, we can store the answer of each recursive call (subproblem) in an array or hashmap so that the next time we need the answer to that subproblem, we can directly fetch it from there instead of calculating it again.

Time Complexity

O(2^N), where N is the number of houses.

 

At each of the N houses, we have two options, hence for each recursive call there will be two further calls.

Space Complexity

O(N), where N is the number of houses.

 

A recursion stack is required to keep track of all recursive calls which takes O(N) memory in the system stack.

Code Solution
(100% EXP penalty)
House Robber
Full screen
Console