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 a given array according to the following conditions:
- The robber can’t rob any two consecutive houses. That is, we can’t include two consecutive elements in our sum. If the ith element is added to the result, then (i + 1)th and (i – 1)th element must be excluded.
- The array is circular. So, the first and last element are adjacent to each other too.
Table of Contents
Example
1 5 4 2
7
4 5 6 8 3
13
Approach(Brute Force)
The problem requires us to find the maximum amount of sum that can be produced by adding non-consecutive elements in the array. We can run a Brute force to check every sequence combination containing non-consecutive elements. But, the indices 1st and Nth are actually adjacent. So, we must ensure to not include both of them in our result. Intuitively, we can find the maximum sum from subarray[1 , N – 1] and subarray[2 , N] separately. Now, both the subarrays are linear. The result will be the maximum of the two subarray-sums.
Now, let’s solve the problem for any general linear array. As we assume that the circularity is absent in the array and it is linear starting from the first element and ending at the last, we have got rid of considering first and last element as adjacent.
It is now clear that we can either:
- Include any element in our sum.
- Exclude that element.
In such a case, we can find the sum produced by all the possible sequences having non-consecutive elements. To find all the possible combinations, we can use Recursion and Backtracking. In every recursive call, we will either include the element in our result sum or exclude it. Based on that, if we choose any element at index I, then the next index should be I + 2, I + 3. …. till the last element. Similarly, if we exclude an element at index I, we can call next recursion on index I + 1, to check all possibilities originating from it. In this way, we check the possibilities to include and exclude every element. Also, all elements constituting the sum will be non-consecutive as we jump to every alternate index.
Algorithm
- If the array is empty, return 0;
- If the array has one element
- We can’t partition the array into two parts. So, return the only element in the array
- Maintain a variable, max_sum_possible, which stores the maximum sum possible
- Call recursive function combinations() to check for every subsequence in subarray[1, N – 1] and [2, N]
- combinations() has parameter to store the sum of every subsequence as cur_sum
- If we have crossed the last element if the array, return.
- Now, let’s check all possibilities we can make by including the current index value
- Add current index value to cur_sum
- Run a loop starting from the alternate index so that we can jump to every non-consecutive element from this index
- Call combinations() on these indices
- Let’s check the possibility when the current element is not included
- Subtract current index value from cur_sum, here we backtrack our solution
- Call combinations() on next index, as we have excluded current index
- At every step, we check if cur_sum > max_sum_possible and update it
- Print the result
Implementation of algorithm to solve House Robber II
C++ Program
#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> &a)
{
int n = a.size();
if(n == 0)
return 0;
if(n == 1)
return a[0];
int max_sum_possible = 0 , cur_sum = 0 , end = n - 2;
combinations(a , cur_sum , 0 , end , max_sum_possible);
end++;
combinations(a , cur_sum , 1 , end , max_sum_possible);
return max_sum_possible;
}
int main()
{
vector <int> a = {1 , 5 , 4 , 2};
cout << rob(a) << '\n';
}
Java Program
import java.lang.Math;
class MutableInt
{
public int val;
MutableInt(int x)
{
this.val = x;
}
}
class House_Robber_II
{
static void combinations(int[] a , int cur_sum , int idx , int end , MutableInt max_sum_possible)
{
if(idx > end)
return;
cur_sum += a[idx];
if(cur_sum > max_sum_possible.val)
max_sum_possible.val = 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;
}
static int rob(int[] a)
{
int n = a.length;
if(n == 0)
return 0;
if(n == 1)
return a[0];
int cur_sum = 0 , end = n - 2;
MutableInt max_sum_possible = new MutableInt(0);
combinations(a , cur_sum , 0 , end , max_sum_possible);
end++;
combinations(a , cur_sum , 1 , end , max_sum_possible);
return max_sum_possible.val;
}
public static void main(String args[])
{
int[] a = {1 , 5 , 4 , 2};
System.out.println(rob(a));
}
}
7
Complexity Analysis of House Robber II Leetcode Solution
Time Complexity
O(N.2^N) as we generate every possible subsequence containing non-consecutive elements.
Space complexity
O(N) due to recursive stack frames
Approach(Dynamic Programming)
We discussed in the previous approach that at any particular index, we can
- Include the element in our sum.
- Exclude the element.
Assume ans[i , N] is the maximum sum we can obtain in the range i to N. This result will further depend on ans[i + 2 , N] and ans[i + 1, N]. We can consider every range as a state such that every state further depends on sub-states. It is possible that we need to recursively solve for any particular state again and again to solve other parent state problems. This is an Optimal Substructure. We can also conclude that for an array of size N, the maximum sum that can be obtained from all ‘n’ elements is the max of these two results:
- Optimal result obtained till (N – 1) elements and including the Nth element
- Best result obtained till (N – 1) and excluding the Nth element
We can create a table such that table[i] stores the maximum sum that can be obtained using the subarray[0, i]. But, there are two choices for every index. So, we need to store two different results for cases: when the element is included and when the element is excluded.
Algorithm
- If the array is empty, return 0
- If the array has just one element, return that element
- Create a function robLinear() that returns the maximum sum that can be obtained in a linear array
- robLinear() works as follows:
- Initiate two variables included and excluded as 0, which stores the max results that be obtained by including and excluding the current element respectively
- At every next iteration, included becomes the current element + excluded result of previous element
- Excluded becomes the maximum of included and excluded results of previous element
- Return the maximum of robLinear(1 , N – 1) and robLinear(2 , N)
Implementation of algorithm to solve House Robber II
C++ Program
#include <bits/stdc++.h>
using namespace std;
int robLinear(int l , int r , vector <int> &a)
{
int inc = 0 , exc = 0 , temp;
for(int i = l ; i <= r ; i++)
{
temp = max(inc , exc);
inc = exc + a[i];
exc = temp;
}
return max(inc , exc);
}
int rob(vector <int> &a)
{
int n = a.size();
if(n == 0)
return 0;
if(n == 1)
return a[0];
return max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
}
int main()
{
vector <int> a = {1 , 5 , 4 , 2};
cout << rob(a) << '\n';
}
Java Program
import java.lang.Math;
class House_Robber_II
{
static int robLinear(int l , int r , int[] a)
{
int inc = 0 , exc = 0 , temp;
for(int i = l ; i <= r ; i++)
{
temp = Math.max(inc , exc);
inc = exc + a[i];
exc = temp;
}
return Math.max(inc , exc);
}
static int rob(int[] a)
{
int n = a.length;
if(n == 0)
return 0;
if(n == 1)
return a[0];
return Math.max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
}
public static void main(String args[])
{
int[] a = {1 , 5 , 4 , 2};
System.out.println(rob(a));
}
}
7
Complexity Analysis of solving House Robber II
Time Complexity
O(N), we traverse the array for 2 times. So, we make O(2N) operations, which is linear.
Space complexity
O(1) Only constant space is used for variables.