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

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

.

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

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

Based on this idea, we have code as below:

• 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!

Written by