Loot Houses
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.

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

Question

Loot Houses

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.

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

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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.

Time Complexity: O(2^n)Explanation:

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.

Accepted Answer

Dynamic Programming Approach

We can use dynamic programming to optimize our recursive approach. We store the computed value of maxLoot(i) in a dp array, and we do this for all i between 1 to N. In this way, we can easily obtain back the value when it is required again. Let dp[i] be the maximum value looted after the first i houses, i.e. houses 0 to i - 1.

We can find out how to compute dp[i] from the recurrence relation we found in the recursive approach.

dp[i] = max(dp[i - 1], arr[i - 1] + dp[i - 2])

where dp[i] = 0 if i ≤ 0 and arr[i] represents the value of the i'th house (Note: The houses are 0 indexed)

Space Complexity: O(n)Explanation:

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

Storing the N dp states requires an array of size N.

Time Complexity: O(n)Explanation:

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

There are only N dp states, each of which require O(1) time to compute.

Accepted Answer

DP Space Optimised Approach

Consider building the result array in a bottom-up fashion (computing the result for smaller to larger numbers of houses). We can observe that if we’re at the ith house, we only require the results for the (i - 1)th and the (i - 2)th houses. Hence, instead of maintaining a whole array, we simply keep track of the last two results obtained.

Space Complexity: O(1)Explanation:

O(1).

As we constant space in memory.

Time Complexity: O(n)Explanation:

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

There are only N dp states, each of which require O(1) time to compute.

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.

Input Format :

Output Format :

Note :

Constraints :

Top Internshala Web Developer interview questions & answers

Popular interview questions of Web Developer