Hello, reader 👋🏽 ! Welcome to day 74 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.
Today, I will be picking up LeetCode's daily challenge problem: 198. 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
numsrepresenting the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.E.g.:
[1,2,3,1]=>4[2,7,9,3,1]=>12
💬 Thought Process - Memoization
This problem is similar to those dynamic programming questions where at every recursive call we decide whether to choose or not choose to select the element.
In this case, at every recursive call, we will either rob the house or not rob the house.
At any house, represented by
index, if we do rob then we would have to skipindex+1house and can only rob theindex+2house.And at any house, if we don't rob then we would have to move on to
index+1house and rob that house.We can start this
rob houseordon't rob housedecision from either the last or first house.Since with recursion we usually do a top-down approach, we will start robbing from the last house.
If we rob the house, we can add the money from the current house to the sum. At every call, we shall return the maximum of the two choices.
Below is the recursive tree for the above explanation.
As you can see, the time complexity could be
O(2^n). But we can reduce this because in the tree it is evident that we are doing repeated work.For e.g.
rob(2)orrob(1)are called multiple times. Rather than re-calculating the results, we can just reuse the previously calculated results by caching them.Hence, we'll use a 1D array to cache values that we find for every index.
memo[index]represents that maximum value that can be obtained untilindexwhen we rob or not rob houses from 0 ton-1.
👩🏽💻 Solution - Memoization
- Below is the code for the approach for solving this problem using memoization.
class Solution {
private int[] memo;
public int rob(int[] nums) {
int n = nums.length;
memo = new int[n];
Arrays.fill(memo, -1);
return robHelper(nums, n-1);
}
private int robHelper(int[] nums, int index) {
if(index < 0) return 0;
// if cached result found, return it
if(memo[index] != -1) return memo[index];
// rob the current house
int robNow = nums[index] + robHelper(nums, index-2);
// skip robbing the current house
// rob the previous house
int robPrevious = robHelper(nums, index-1);
// cache result
return memo[index] = Math.max(robNow, robPrevious);
}
}
Time Complexity: O(n)
- m = number of houses
Space Complexity: O(n)
- n = number of houses
💬 Thought Process - Tabulation
We can also solve this problem using DP bottom-up/ tabulation where we will solve for the maximum money robbed from the first to last house.
We will use a 1D array to tabulates the values calculated for previous houses and then use it for robbing the current or future houses.
- We'll work our way from first to the last house.
👩🏽💻 Solution - Tabulation
- Below is the code for the approach for solving this problem using tabulation.
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
for(int i = 0; i<n; i++) {
int curr = nums[i];
// rob the current house
int robNow = curr;
// If there exists a previous house,
// use the money robbed there
if(i-2 >= 0) {
robNow += dp[i-2];
}
// don't rob the current house
int robPrevious = 0;
// If there exists a previous house,
// use the money robbed there
if(i-1 >= 0) {
robPrevious = dp[i-1];
}
// tabulate the max of the money robbed so far
dp[i] = Math.max(robNow, robPrevious);
}
return dp[n-1];
}
}
Time Complexity: O(n)
- m = number of houses
Space Complexity: O(n)
- n = number of houses
💬 Thought Process - Space optimisation
- Since we only require the money robbed until houses
index-1andindex-2to calculate the maximum atindex, we can use variables to store these values rather than tabulating for all the n houses.
👩🏽💻 Solution - Space optimisation
- Below is the code for the approach for solving this problem using space optimisation.
class Solution {
public int rob(int[] nums) {
int n = nums.length;
// Edge cases: when there are 1 or 2 houses
if(n == 1) return nums[0];
if(n == 2) return Math.max(nums[0], nums[1]);
int[] dp = new int[n];
// dp[0] represents robbing the first house
// dp[1] represents robbing either the first or second house
int first = nums[0], second = Math.max(nums[0], nums[1]);
for(int i = 2; i<n; i++) {
int curr = nums[i];
// rob now with the help of i-2 house
int robNow = curr + first;
// what is beneficial?
// robbing this house or not robbing this house?
int max = Math.max(robNow, second);
// update the i-2 and i-1 max values
first = second;
second = max;
}
return second;
}
}
Time Complexity: O(n)
- n = number of houses
Space Complexity: O(1)
- You can find the link to the GitHub repo for this question here: 198. House Robber.
Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!
Thank you for reading!