Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1: Brute Force
3.1.
Code
3.2.
Complexity Analysis
4.
Approach 2: Dynamic Programming
4.1.
Code
4.2.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
Why did we consider two cases here?
5.2.
What is the most optimized approach for the House Robber 2 problem?
5.3.
Why did we initialzed dp[0] = 0 ?
6.
Conclusion
Last Updated: Mar 27, 2024
Hard

House Robber 2

Author Rhythm Jain
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

​​​​In the “House Robber II” problem, a robber wants to rob money from different houses. The amount of money in the houses is represented through an array. We need to find the maximum sum of money that can be made by adding the elements in the given array. The array is circular, and the robber can’t rob two adjacent houses.

House Robber 2 is a problem based on dynamic programming, i.e., quite an important topic in the data structure for interviews. At first, the problem may seem confusing, but as soon as you realize the constraints, it is a cakewalk.

Lets Go Lets Move GIF - Lets Go Lets Move Get Ready - Discover & Share GIFs

Source: Giphy

Problem Statement

Mr. X is a skilled burglar who intends to loot houses along a street. Each home has a specific amount of money tucked away. All of the residences in this area are grouped in a circle. That is, the first home is next to the final one. Meanwhile, nearby houses are connected to a security system, which will immediately inform the police if two adjacent houses are broken into on the same night.

Given an integer array nums indicating the amount of money in each house. Return the greatest amount of money Mr. X can rob without notifying the cops.

Example:

Input:

[2, 3, 2]

Output:

3

Explanation:

Mr.X cannot rob house 1 and then rob house 3 because they are adjacent houses. So maximum will be picking only one house to rob, i.e., house 2 with maximum money = 3.

House Arrangements

 

Recommended: Please try it on “Coding Ninjas Studio” before moving on to the solution approach.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1: Brute Force

The task is to determine the greatest amount of sum formed by adding non-consecutive array members. We can use brute force to examine any sequence combination that has non-consecutive components. The indices 1st and Nth, however, are genuinely adjacent. As a result, we must take care not to include both of them in our conclusion. We may independently deduce the highest sum from subarray[1, N – 1] and subarray[2, N]. Both subarrays are now linear. The total of the two subarray-sums will be the outcome.

We can use recursion. In each recursive call, we shall either include or omit the element from our result total. If we select any element at index I, the following index should be I + 2, I + 3, and so on until we reach the last index. Similarly, if we exclude an element at index I, we may use the following recursion on index I + 1 to examine all possibilities that arise from it. In this manner, we examine the options for including and excluding each element. In addition, when we go to each alternate index, all of the items that make up the total will be non-consecutive.

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void combinations(vector <int> &a , int &cur_sum , int idx , int end , int &max_sum_possible)
{
    if(idx > end)
        return;
    cur_sum += a[idx];
    if(cur_sum > max_sum_possible)
        max_sum_possible = cur_sum;
    for(int i = idx + 2 ; i <= end ; i++)
        combinations(a , cur_sum , i , end , max_sum_possible);
    cur_sum -= a[idx];
    combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
    return;
}
int rob(vector <int> &houses)
{
    int n = houses.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return houses[0];
    int max_sum = 0 , cur_sum = 0 ;
    combinations(houses , cur_sum , 0 , n-2 , max_sum);
    combinations(houses , cur_sum , 1 , n-1 , max_sum);
    return max_sum;
}
int main()
{
    vector <int> a = {2,3,3};
    cout << rob(a) << '\n';
}

Output:

3

Complexity Analysis

Time Complexity: O(N.2N)

Due to the generation of all possible combinations of robbing houses.

Space Complexity: O(N)

Due to Recursive Stack Frames.

Approach 2: Dynamic Programming

The important thing is that you can't rob both the first and last houses at the same time.

As a result, the key concept is to use dynamic programming. In this section, we will look at two scenarios:

  1. When you first rob a house,
  2. When you don't rob the first house, but rather the last.

The dynamic programming approach that must be used with two arrays, given array ARR and new array DP, to store values till the ith house is as follows:

  1. Set DP[0] to 0 and DP[1] to ARR[1].
  2. Iterate on the houses.
  3. You have two possibilities at the ith house:
    1. Rob the (i-1)th (prior) home, but skip the ith house, i.e. DP[i-1].
    2. Rob the ith home after the (i-2)th, skipping the (i-1)th, resulting in DP[i-2] +ARR[i].
  4. Select the maximum of DP[i-1] and DP[i-2] + ARR[i].
  5. Return the money you obtained after the last home.

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*
    Time Complexity: O(N)
    Space complexity: O(N)
    
    where 'N' is the length of array.
*/
long long int houseRobberUtil(vector<int> valueInHouse, int start, int end)
{

    long long int valueAtIthHouse[valueInHouse.size()];

// Check if the thief may steal the first house or not.
    if (start == 0)
    {
        valueAtIthHouse[0] = valueInHouse[0];
        valueAtIthHouse[1] = max(valueInHouse[0], valueInHouse[1]);
    }

    else
    {
        valueAtIthHouse[0] = 0;
        valueAtIthHouse[1] = valueInHouse[1];
    }

    for (int i = 2; i < end; i++)
    {
        valueAtIthHouse[i] = max(valueAtIthHouse[i - 2] + valueInHouse[i], valueAtIthHouse[i - 1]);
    }

    return valueAtIthHouse[end - 1];
}
int rob(vector <int> &houses)
{
    if (houses.size() == 0)
    {
        return 0;
    }

    if (houses.size() == 1)
    {
        return houses[0];
    }
    return max(houseRobberUtil(houses,0, houses.size() - 1), houseRobberUtil(houses, 1, houses.size()));
}
int main()
{
    vector <int> a = {2,3,3};
    cout << rob(a) << '\n';
}

Output:

3

Complexity Analysis

Time Complexity: O(N)

Because we'll have to go through the full array twice.

Space Complexity: O(N)

Because we'll be making an auxiliary array to keep track of the total amount stolen for each residence.

Soon after this, you can practice one more version of this problem, Loot Houses, which will surely be a cakewalk for you.

Check out Longest Common Substring

Let's wrap up this article and move toward the FAQs section.

Frequently Asked Questions

Why did we consider two cases here?

We considered two cases because, since the first and last house cannot be robbed simultaneously (because the array is circular so they would become adjacent) therefore, we considered two cases, one taking the first house and not the last; another case including the last house and not first.
 

What is the most optimized approach for the House Robber 2 problem?

The most optimized approach is linear space and time complexity using dynamic programming.
 

Why did we initialzed dp[0] = 0 ?

We initialized dp[0] = 0 because dp[i] indicated the solution of the problem when we have i number of houses. Since dp[0] indicates solution when we have zero houses, that is why dp[0] is initialized to 0.

Conclusion

Dynamic Programming has always reduced huge time complexities and provided us with the most efficient solution. But note that dynamic programming can only be applied when we can observe some repeated subproblems.

You can study more about Dynamic Programming by visiting Dynamic Programming and Algorithms. If you wish to practice questions based on Dynamic Programming, check out Top Dynamic Programming Questions.

Check out this problem - Minimum Coin Change Problem 

I hope that this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem and if you would like to learn more, check out our articles on the Coding Ninjas Studio. Also, check out our courses and look at the interview experiences and interview bundle for placement preparations.

Happy Coding!!

Previous article
House Robber
Next article
Maximize Subsequence Sum after a Plus-Minus Sign Alternatively on Elements
Live masterclass