Loot Houses — Asked in Samsung and Amazon Interview

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.

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.

Sample Input:

4
10 2 3 11

Output:

21

Explanation of given Test Cases :

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.

Approach :

We can use dynamic programming to optimize our recursive approach but that would give us space complexity of O(N) so we will use a space optimized DP to bring down the space complexity.

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.

Time Complexity: O(N)
Space Complexity: O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.