This content originally appeared on DEV Community and was authored by Alkesh Ghorpade
Problem statement
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight **without alerting the police**.
Example 1:
Input: nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
- 1 <= nums.length <= 100
- <= nums[i] <= 400
Explanation
Dynamic programming
We can reduce the problem to find the maximum sum subsequence where no two selected elements are adjacent. The approach to the problem is using Dynamic programming. So there are two cases.
- If the element is selected the next adjacent element cannot be selected.
- If an element is not selected then the next element can be selected.
A C++ snippet of the above approach is as below:
int rob(vector<int>& nums ){
int n = nums.size();
if (n == 0)
return 0;
if (n == 1)
return nums[0];
if (n == 2)
return max(nums[0], nums[1]);
int dp[n];
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i<n; i++)
dp[i] = max(nums[i]+dp[i-2], dp[i-1]);
return dp[n-1];
}
The time and space complexity of the above approach is O(N).
Efficient approach: using two variables
If we carefully look at the dynamic programming approach we observe that the values of the previous two indices matter while calculating the value for an index. We can replace the DP array with two variables.
Let's check the algorithm first.
- set evenSum, oddSum = 0, 0
- loop for i = 0; i < nums.size(); i++
- if i % 2 == 0 // even index
- evenSum += nums[i]
- evenSum = evenSum > oddSum ? evenSum : oddSum
- else
- oddSum += nums[i]
- oddSum = evenSum > oddSum ? evenSum : oddSum
- return evenSum > oddSum ? evenSum: oddSum
The time complexity of the above approach is O(N) and space complexity if reduced to O(1).
C++ solution
class Solution {
public:
int rob(vector<int>& nums) {
int evenSum = 0, oddSum = 0;
for(int i = 0; i < nums.size(); i++){
if(i % 2 == 0){
evenSum += nums[i];
evenSum = evenSum > oddSum ? evenSum : oddSum;
} else {
oddSum += nums[i];
oddSum = evenSum > oddSum ? evenSum : oddSum;
}
}
return evenSum > oddSum ? evenSum: oddSum;
}
};
Golang solution
func rob(nums []int) int {
evenSum, oddSum := 0, 0
for i := 0; i < len(nums); i++ {
if i % 2 == 0 {
evenSum += nums[i]
if evenSum < oddSum {
evenSum = oddSum
}
} else {
oddSum += nums[i]
if oddSum < evenSum {
oddSum = evenSum
}
}
}
if evenSum > oddSum {
return evenSum
}
return oddSum
}
Javascript solution
var rob = function(nums) {
let evenSum = 0, oddSum = 0;
for(let i = 0; i < nums.length; i++) {
if( i % 2 == 0 ) {
evenSum += nums[i];
evenSum = evenSum > oddSum ? evenSum : oddSum;
} else {
oddSum += nums[i];
oddSum = evenSum > oddSum ? evenSum : oddSum;
}
}
return evenSum > oddSum ? evenSum : oddSum;
};
Let's dry-run our algorithm to see how the solution works.
Input: nums = [2, 7, 9, 3, 1]
Step 1: evenSum = 0
oddSum = 0
Step 2: loop for i = 0; i < nums.size()
0 < 5
true
i % 2 == 0
0 % 2 == 0
true
evenSum = evenSum + nums[i]
= 0 + nums[0]
= 2
evenSum = evenSum > oddSum ? evenSum : oddSum
= 2 > 0
= true
= 2
i++
i = 1
Step 3: loop for i < nums.size()
1 < 5
true
i % 2 == 0
1 % 2 == 0
false
oddSum = oddSum + nums[i]
= 0 + nums[1]
= 7
oddSum = evenSum > oddSum ? evenSum : oddSum
= 2 > 7
= false
= 7
i++
i = 2
Step 4: loop for i < nums.size()
2 < 5
true
i % 2 == 0
2 % 2 == 0
true
evenSum = evenSum + nums[i]
= 2 + nums[2]
= 2 + 9
= 11
evenSum = evenSum > oddSum ? evenSum : oddSum
= 11 > 7
= true
= 11
i++
i = 3
Step 5: loop for i < nums.size()
3 < 5
true
i % 2 == 0
3 % 2 == 0
false
oddSum = oddSum + nums[i]
= 7 + nums[3]
= 7 + 3
= 10
oddSum = evenSum > oddSum ? evenSum : oddSum
= 11 > 10
= true
= 11
i++
i = 4
Step 6: loop for i < nums.size()
4 < 5
true
i % 2 == 0
4 % 2 == 0
true
evenSum = evenSum + nums[i]
= 11 + nums[4]
= 11 + 1
= 12
evenSum = evenSum > oddSum ? evenSum : oddSum
= 12 > 11
= true
= 12
i++
i = 5
Step 7: loop for i < nums.size()
5 < 5
false
Step 8: return evenSum > oddSum ? evenSum : oddSum
12 > 11
true
So we return the answer as 12.
This content originally appeared on DEV Community and was authored by Alkesh Ghorpade
Alkesh Ghorpade | Sciencx (2022-01-02T18:15:02+00:00) LeetCode – House Robber. Retrieved from https://www.scien.cx/2022/01/02/leetcode-house-robber/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.