Day 3 : House Robber 2

You are tasked with robbing houses arranged in a circular layout, where adjacent houses trigger an alarm if robbed on the same night. 

Given an array nums representing the money in each house, return the maximum amount you can rob without alerting the police.

Before we get started let's take a deep breath…This is f%$! hard but it’s worth doing if you want to pursue a career in tech.

It took me some good time to wrap my head around this problem, so let’s take it step by step!

• What are we asked? Find the max amount of money we can rob without getting caught! 🤑

• Remember, you cannot rob two adjacent houses, so you must carefully evaluate these options to maximize your gains. What do we need to calculate at each step? At each step, the goal is to maximize the total amount robbed. Does it make more sense to rob the current house, but skip the adjacent one, or skip the current one?

   

Now before we continue, an approach I tried was directly comparing the value of nums[0] and nums[nums.size()-1] . That won’t work, because the circular layout changes the combinations of houses you can rob, and the max profit can be different even if you get the highest value from both houses right off the bat.

So the way to go is to calculate the profit you would get if you robbed the first house and the profit if you robbed the last house and compare.

For this tutorial, we will only demonstrate robbing the first house and you can repeat the same process to rob the last house.

Let's look at an example with [2,7,9,3,1] :

The sequence builds up like this:

1. dp[0] = 2

2. dp[1] = 7

3. dp[2] = cost[2] + max((dp[0]+nums[2]), dp[1]) 

We start by initializing an array dp where dp[i] represents the maximum amount we can rob up to house i. We'll set:

• dp[0] = nums[0] (rob the first house)

• dp[1] = max(nums[0], nums[1]) (maximum of first two houses)

Then we build the array up 🏗️, solving one house at a time from 2 up to n. For each house i:

1. We consider both options at house i:

   • Skip this house (take the previous best)

   • Rob this house (take best from two houses back + current house)

2. Keep track of the maximum result found and store it in dp[i]

To track the maximum result at each house:

• dp[i] - current best (maximum) amount we can rob up to house i

• dp[i-1] - maximum if we skip the current house

• dp[i-2] - maximum if we rob current house (must add nums[i])

• nums[i] - the amount in current house

• dp[i-2] + nums[i] - adds current house to best from two back

• max(dp[i-1], dp[i-2] + nums[i]) - keeps maximum between skipping or robbing

This gives us our formula: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

To solve for the circular array, we simply add and extract the process to a function and call it twice:

• Once with start being set to 0 and end to second to last house (we can’t rob the last house)

• Once with start being set to 1 and end to the last house (we can’t rob the first house)

Finally, our answer lies in the max of both of these results.

class Solution {
public:
   
    int auxRob(vector<int>& nums, int start, int end) {
        int n = end - start + 1;
        if (n == 1) return nums[start];

        vector<int> dp(n);
        dp[0] = nums[start];
        dp[1] = max(nums[start], nums[start + 1]);

        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i]);
        }

        return dp[n - 1];
    }

    int rob(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0]; 
        }
        else if (nums.size() == 2) {
            return max(nums[0], nums[1]); 
        }
        
        
        int robbingFirst = auxRob( nums, 0, nums.size()-2);
        int robbingLast = auxRob( nums, 1, nums.size()-1);
       
        
        return max(robbingFirst,robbingLast); 
    }
};

Let me invoke you into my cult

Media worth seeing

1. NeetCode 250 List, I love this list, I love the roadmap, and overall love NeetCode.

2. If you didn’t believe me when I said Software is extremely political, joke is on you 😆 . Apple, TikTok, Meta, Tesla… all Tech Bros were united in Trump’s inauguration.

Hacks of the week

I truly believe you can gaslight yourself to success.

1. I gave myself today a high-five in the mirror and I’m happy to report, it was a complete highlight

2. 6 Steps to completely dominate LeetCode 

3. The hatch alarm has become my newest secret obsession

4. You have anxiety because deep down you know you could be doing bigger things

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!