198. House Robber Leetcode Solution
House Robber Leetcode Problem :
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.
Lowest Common Ancestor of a Binary Tree Leetcode Solution :
Constraints :
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400
Example 1:
- Input: nums = [2,7,9,3,1]
- Output: 12
Intution :
Here we are applying a bottom approach (Dynamic Programming) for reducing space complexity to O(1). If we try to notice closely, we realise that at every index we only need the results of the previous two positions, i.e. for ‘INDEX’ – 2 and ‘INDEX’ – 1. Hence we do not need to store the results in an array/list, and rather we can store it into the two variables.
Approach :
- We assign two variables ‘prevFirst’ and ‘prevSecond’, Where ‘prevFirst is the cumulative sum till (’INDEX’ – 1)th elements and ‘prevSecond’ is the cumulative sum till (‘INDEX’ – 2)th elements.
- Consider two options to either include or exclude the ‘CURR’ element, i.e. ‘ARR[INDEX]’ in our subsequence, and we have two options:
- Including the ‘CURR’ element, optionA = ‘prevSecond’ + ‘ARR[INDEX]’
- Excluding the ‘CURR’ element, optionB = ‘prevFirst’.
- Return max( optionA, optionB)
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int rob(vector< int>& nums) {
int n = nums.size();
// Two variables to store the previous results.
int prevFirst = 0;
int prevSecond = 0;
for (int i = 0; i < n; i++){
int temp = prevFirst;
prevFirst = max(prevSecond + nums[i], prevFirst);
prevSecond = temp;
}
return prevFirst;
}
};
class Solution {
public int rob(int[] nums) {
int l = nums.length;
if(l==1) return nums[0];
if(l==2) return Math.max(nums[0],nums[1]);
if(l==3) return Math.max(nums[0]+nums[2],nums[1]);
int[] res = new int[l];
res[0] = nums[0];
res[1] = nums[1];
res[2]= nums[0]+nums[2];
for(int i=3;i< l;i++)
{
res[i]= Math.max(res[i-2]+nums[i] , res[i-3]+nums[i]);
}
return Math.max(res[l-1],res[l-2]);
}
}
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root == p or root == q:
return root
l = self.lowestCommonAncestor(root.left, p, q)
r = self.lowestCommonAncestor(root.right, p, q)
if l and r:
return root
return l or rclass Solution:
def rob(self, nums: List[int]) -> int:
# Base case
if len(nums) < 3: return max(nums)
# M(emory) stores maximum money until last two points
M = nums[0], max(nums[0], nums[1])
# We iterate M until we get the max money in the last house
for i in range(2, len(nums)):
# Only store last two points to save memory
M = M[1], max(nums[i]+M[0], M[1])
return M[1]Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment