House Robber II (LeetCode #213)

Image by Patrick Loonstra 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 II 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. The houses are in a circle (meaning the first one is next to the last one), so stealing from the first and last houses count as houses next to each other and will set off an alarm
4. We must return the maximum amount of money we can rob in a single night without setting off any security systems
5. The length of nums (the houses) will be 1 <= len(nums) <= 100
6. The value at each index of nums will be 0 <= nums[i] <= 1000

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.

Let’s get to it. 🔥

Initial Setup ☝🏻

This problem is extremely similar to the first House Robber problem (like, almost the same except with a few tweaks). I’d recommend reading my article on that problem first to understand how it works. In fact, the only thing that differentiates it is the fact that our houses are now in a circle.

This means that we can only ever rob the first or the last house, never both.

See where I’m going with this?

What if we were to encapsulate our logic for checking all the houses in a function and then run that function with our list of houses — first with the initial house removed, and then with the last house removed.

If we did this, it should reveal to us which amount is greater.

Okay. We have a game plan.

Let’s start by setting up our function and handling cases where we have one or less houses:

This will return 0 if our nums list has no length. If there is one house, we’ll just return the value in it.

From here, we’ll go on to our next step of creating a reusable internal function we can call multiple times to find our optimal house amounts.

Building a Reusable Function 🌀

Next, let’s initialize a new function inside our rob function that we can call multiple times:

If you read through my article on the original House Robber problem, you might already recognize this. We’re going to be using the same code here inside our internal function.

First, we initialize our max_robbed variable with the maximum value in the houses list passed in as an argument. It will help us prevent errors.

The next step we need to do is set up a dynamic programming list (dp) that we can use to track optimal robbery amounts as we iterate through it.

Lastly, we need to set up a lookbacks list with 2 and 3. We can’t look back at the previous index 1, and we won’t want to skip houses unnecessarily. Therefore, we want to choose the totals either 2 or 3 houses behind the one we’re currently looking at.

As an example, say we had a list of homes like this:

[5, 3, 7, 2, 4, 1]

If we start at index 0 and look at each home, eventually we’ll get to index 3 where we can actually look back at the indices 1 and 0 (for look backs of 2 and 3):

[5, 3, 7, 2, 4, 1]
 ^  ^     ^ <-------- Current index looking back at 5 and 3

The value we choose will be one of these numbers. If we were to keep going (to 4 and 1 in the list above), we still would want to choose either the look back of 2 or 3 indices as anything more than that would be skipping homes that we’d want to rob.

[5, 3, 7, 2, 4, 1]
    ^  ^     ^ <-------- Current index looking back at 3 and 7

The next thing we want to do is add the inner loops for our internal function:

First, we iterate over the entire dp list that we created earlier.

Second, we look backwards for every l in the lookbacks list (which is a constant of 2 and 3).

Lastly, we check if the current i index minus the look back l is greater-than-or-equal-to 0. If it is, we set the current dp index position we’re at to the maximum of either that current position or the house value plus whatever the look back value is in the dp list.

Once all of this is done, we then update our max_robbed variable to be the maximum of either its current value or the dp list’s current index that we just set.

When our loops have finished running, we can merely return the max_robbed amount that we’ve calculated out.

Using Our Function 🎡

Nice. Now that we have this function, we’re 90% of the way there to finishing this coding challenge.

Our final steps are to run this function twice. The first time will be without the first house, and the second time will be without the last house (because we can either rob the first house or the second house).

This is what that looks like in code form:

If you haven’t seen list slices before in Python, that [1:] style of syntax allows us to slice the list starting at index 1. A similar thing happens with the [:len(nums) — 1] except we slice up to the index of len(nums) — 1.

Finally, we just write a ternary if/else statement to returns whichever of these two total amounts is greatest.

BOOM.

There you go. That’s the answer.

This will run in a time complexity of O(n) (since our lookbacks list is a constant list equivalent to two if statements) and a space complexity of O(n) for the duplication of our houses list while slicing or the creation of the dp lists inside our internal functions.

Conclusion

I hope you enjoyed this one. LeetCode challenges can be a bit frustrating, but they can be personally rewarding once you understand them (kind of like the itch some people get for solving Sudoku).

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 and music recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)