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 :

1. 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.
2. Consider two options to either include or exclude the ‘CURR’ element, i.e. ‘ARR[INDEX]’ in our subsequence, and we have two options:
3. Including the ‘CURR’ element, optionA = ‘prevSecond’ + ‘ARR[INDEX]’
4. Excluding the ‘CURR’ element, optionB = ‘prevFirst’.
5. Return max( optionA, optionB)

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

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