Crack Leetcode 198: House Robber

There is a way to make it easy.

3 min readNov 13, 2020

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:

(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?

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):

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

Based on this idea, we have code as below:

Python Code:

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).