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

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

**and**

*(**i-1*),*maxRobAmount*in house

**(**

*i-2*):maxRobAmount(i) =

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

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

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

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