House Robber II

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
311 upvotes
Asked in companies
UberGoogleIntuit

Problem statement

Mr. X is a professional robber planning to rob houses along a street. Each house has a certain amount of money hidden.


All houses along this street are arranged in a circle. That means the first house is the neighbour of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses are broken into on the same night.


You are given an array/list of non-negative integers 'ARR' representing the amount of money of each house. Your task is to return the maximum amount of money Mr. X can rob tonight without alerting the police.


Note:
It is possible for Mr. X to rob the same amount of money by looting two different sets of houses. Just print the maximum possible robbed amount, irrespective of sets of houses robbed.


For example:
(i) Given the input array arr[] = {2, 3, 2} the output will be 3 because Mr X cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses. So, he’ll rob only house 2 (money = 3)

(ii) Given the input array arr[] = {1, 2, 3, 1} the output will be 4 because Mr X rob house 1 (money = 1) and then rob house 3 (money = 3).

(iii) Given the input array arr[] = {0} the output will be 0 because Mr. X has got nothing to rob.
Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.

The first line of each test case contains an integer, ‘N’ representing the size of the first array/list.

The second line of each test case contains 'N' single space-separated integers representing the array/list elements.
Output Format :
For each test case, print a single line containing a single integer denoting the maximum money that can be robbed in a separate line.

The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 5 x 10 ^ 3
1 <= ARR[i] <= 10 ^ 9

Time limit: 1 sec.
Sample Input 1:
3
1
0
3
2 3 2
4
1 3 2 1
Sample Output 1:
0
3
4
Explanation of Input 1:
(i) Mr. X has only one house to rob, but with no money.

(ii) Mr. X cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses (remember, it’s a circular street). So, he’ll rob only house 2 (money = 3) with a maximum value

(iii) Mr. X will get maximum value when he robs house 2 (money = 3) and then robs house 4 (money = 1) i.e. 4 units of money.
Sample Input 2:
3
5
1 5 1 2 6
3
2 3 5
4
1 3 2 0
Sample Output 2:
11
5
3
Hint

Think about how you can use the solution to smaller subproblems to solve larger problems.

Approaches (1)
Dynamic Programming

The main point is that you can't rob both the first and the last houses.

Therefore, the core idea is to apply dynamic programming. Two cases are considered here: 

  • When you rob the first house
  • When you don't rob the first house, i.e. you rob the last one.

 

The dynamic programming  algorithm that must be applied considering two arrays, given array ARR and new array DP to store value till the ith house is:

  1. Initialize DP[0] to 0 and DP[1] = ARR[1]
  2. Iterate over houses
  3. At the ith house you have two options:
    • Keep the money from the (i-1)th (previous) house, skipping the ith house, i.e. DP[i-1]
    • Rob the ith house after the (i-2)th house, skipping the (i-1)th i.e. DP[i-2]+ARR[i]
  4. Choose the most profitable option i.e. Maximum of DP[i-1] and DP[i-2] + ARR[i]
  5. Return the sum you've got after the last house
Time Complexity

O(N), where ‘N’ is the length of the array. 

 

Because we’ll be traversing the entire array twice.

Space Complexity

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

 

Because we’ll be creating an auxiliary array to store the maximum amount robbed for every house.

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