Crack Leetcode 198: House Robber

There is a way to make it easy.

Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 198 — House Robber— together. Without further ado, let’s get started.

Problem Description:

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
(photo taken from Leetcode: https://leetcode.com/problems/house-robber/)

Ideation:

Suppose now we are in house i. Then, we consider, if we can safely rob house i, and we choose to rob it, how much would the sum be? If we don’t rob house i, how much would the sum be? Which one is greater?

Image for post
Image for post

From these questions, we can see the calculation of max amount we can rob up to house i depends on the previous condition. Therefore we need a recurrence relation.

There are two ways for that:

Solution #1:

We can relate maxRobAmount in house i, to maxRobAmount in house (i-1), and maxRobAmount in house (i-2):

Image for post
Image for post

maxRobAmount(i) = max( maxRobAmount(i-1), maxRobAmount(i-2)+ amount In House i )

Based on this idea, we have code as below:

Python Code:

Image for post
Image for post

.

Complexity Analysis:

  • Time Complexity:

Doesn’t matter in best-case or worst-case, we all need to go over nums for once. Therefore, time complexity is O(N).

  • Space Complexity:

Since we initiated an array with length N, the auxiliary space we need is O(N). Therefore, the Space Complexity is O(N).

.

Solution#2:

Instead of using an array to store all previous maxRobAmount, we can relate maxRobAmount(i) to (i-1) only. So that we can reduce the space complexity to O(1).

This is realized by storing more than one states in house(i-1). Variable#1: a variable maxRobAmount, and Variable#2: noRob, which essentially is maxRobAmount(i-2).

Image for post
Image for post

And the relation of i and (i-1) is like this:

Image for post
Image for post

Based on this idea, we have code as below:

Python Code:

Image for post
Image for post

Complexity Analysis:

  • Time Complexity:

Doesn’t matter in best-case or worst-case, we all need to go over nums for once. Therefore, time complexity is O(N).

  • Space Complexity:

Since we used constant auxiliary space, the Space Complexity is O(1).

The End:

Thanks for reading! Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!

Life is beautiful!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store