House Robber (LeetCode #198)

Image by Michael Dziedzic on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Coin Change.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode House Robber problem, you’re in the exact right place.

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.

Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.

Let’s get it started!

Understanding the Problem 🤨

The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):

1. We’ll be given a list of houses on the street where each index represents the house and the value at that index represents the amount of money stashed at that house
2. If two houses next to each other are robbed on the same night, the security systems will be set off
3. We must return the maximum amount of money we can rob in a single night without setting off any security systems
4. The length of nums (the houses) will be 1 <= len(nums) <= 100
5. The value at each index of nums will be 0 <= nums[i] <= 400

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

Okay. I think that’s all the housekeeping items we need to discuss before we jump in.

Let’s do it.

Initial Setup 🧱

This problem is another dynamic programming one! If you’re anything like me, these problems can seem super intimidating when you are first learning the patterns to them.

This problem is also very similar to the Coin Change problem that I recently wrote about, so feel free to check that one out first if you want a good baseline on what we’re about to do.

The first thing we want to do is set up our variables. Let’s do that and then I’ll go over why we set them up that way:

First off, we’re finding out what the maximum value is in the nums list and setting our final variable for the answer (max_total) to this. This gives us a fallback in case there’s only one or two houses in the list of nums.

Second, we initialize a dynamic programing list that initially will just have the values of nums in it.

Finally, we set up a list of lookbacks to use (this is similar to the coins list in the Coin Change problem I mentioned above). The only important rule here is that we can’t check neighboring houses for each index, so I chose to use 2 and 3 as the look backs.

Okay, that’s our initial setup. If some of this seems confusing, don’t worry. We’ll get into the specifics in just a bit!

Building Our Loops 🔄

First, we need to iterate over every value in our nums list and get the index i.

Second, we need to look backwards for every l in our lookbacks list (which is just 2 and 3).

Here’s what that looks like:

For each of these look backs, we want to check if the current house index i from our nums loop minus the l look back number (2 or 3) is greater-than-or-equal-to 0.

If it is, we want to do two things:

1. Set the dp list equal to the max of either the current dp[i] or the total of nums[i] (the current house’s money value at i) plus dp[i — l] (the house at the look back value).
2. Set max_total equal to the max of either its current value or dp[i]

Here’s what that looks like in code form:

Boom.

We’re essentially looking at every house and looking 2 or 3 houses backwards (not 1 since that would set off an alarm) in order to see what the biggest money total is we can steal.

The last thing we want to do return our max_total:

This solution will run in O(n) time complexity (where n is the length of the nums list) since our lookbacks inner loop is always a constant group (equivalent to two if statements) and also have a O(n) space complexity (for the dp list of the length of nums).

Conclusion

Congrats on making it through this one!

Keep an eye out for the rest of these Blind 75 coding challenges articles. It’s going to be a fun ride.

Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)