An Interest In:
Web News this Week
- April 23, 2024
- April 22, 2024
- April 21, 2024
- April 20, 2024
- April 19, 2024
- April 18, 2024
- April 17, 2024
Some of Our Sources
- Technology Review
- Just Creative
- Pearsonified
- Smashing Magazine
- Inspiredology
- My Ink Blog
- Web Design Ledger
- Web Resource Source
- Codrops
- Hashedout
Help Webnuz
Referal links:
LeetCode - House Robber
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: 4Explanation: 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: 12Explanation: 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] <= 400Explanation
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: oddSumThe 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 = 0Step 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 = 1Step 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 = 2Step 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 = 3Step 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 = 4Step 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 = 5Step 7: loop for i < nums.size() 5 < 5 falseStep 8: return evenSum > oddSum ? evenSum : oddSum 12 > 11 trueSo we return the answer as 12.Original Link: https://dev.to/_alkesh26/leetcode-house-robber-53em
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To