## CodeFights Solves It: houseRobber

This week’s Interview Practice Task of the Week is houseRobber, a technical interview question that’s been asked at LinkedIn. In this challenge, we’re asked to assist a robber in stealing from houses. Not something that we recommend you do in real life, of course! We will be looking at an (inefficient) recursive solution and then seeing how we can speed it up using memoization (not a typo!) or dynamic programming.

In this task, we are given an array `loot`

, where `loot[i]`

represents the total value of goods we can take from house `i`

. Each house is connected to its neighbors, so the robber isn’t willing to rob two neighboring houses. This means if we take the loot from house `i`

, houses `i-1`

and `i+1`

are off limits! Our task is to write a function `houseRobber(loot)`

that returns the maximum amount of loot the robber can steal given `loot`

.

For example, if `loot = [5,10,12,2]`

then the maximum amount of loot that the robber can take is 17 (stealing `5`

from house 0 and `12`

from house 2). If we had the same values in a different order such as `loot = [5,10,2,12]`

, then the maximum amount the robber can take jumps up to 24 (stealing `10`

from house 1 and `12`

from house 2).

These examples are a little misleading, however. They suggest that we look at stealing from the even numbered houses, and compare that to what we would get stealing from the odd numbered houses. While stealing from evens or odds will ensure we visit the maximum *number* of houses, it doesn’t guarantee maximum value. For example:

1 2 3 4 5 |
loot = [10,5,2,12] strategy: stealing from even houses nets 10 + 2 = 12 stealing from odd houses nets 5 + 12 = 17 best solution is to rob first and last house: 10 + 12 = 22 |

In the problem we are guaranteed that each house has a non-negative amount of money.

## Recursive solution

Let’s start by looking at a few cases. First, we’ll look at a few trivial cases:

- If there are no houses (i.e.
`loot = []`

) then the robber is out of luck and gets nothing. We return 0. - If there is only one house, then the solution is obvious: take whatever is inside, so we return
`loot[0]`

. - If there are two houses, then the robber should steal from the house that has the most money, so we should return
`max(loot[0], loot[1])`

.

These are called our base cases.

Here comes the magic part: what if we have `N`

houses, where `N > 2`

? Let’s start at the first house: we have to decide whether the robber should rob this house or not. Our two choices are:

- Steal from the first house. Then we cannot steal from the second house. The best we will be able to get is the value from this house (
`loot[0]`

) plus whatever we can get from house 3 onward (because the second house is off-limits). So our payoff is`loot[0] + houseRobber(loot[2:])`

. - Don’t steal from the first house. Then this problem is identical to ignoring the first house altogether, and evaluating
`houseRobber(loot[1:])`

(ignoring the first house, and solving the same problem from second house).

We should evaluate both choices, and return the larger of the two. Notice that regardless of which step we make, the problem gets smaller on each step. Eventually we’ll end up with 0, 1, or 2 houses in our list, and the base cases will actually evaluate our solution.

Here’s the recursive solution in code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
def houseRobber(loot): # our base cases if len(loot) == 0: return 0 if len(loot) == 1: return loot[0] if len(loot) == 2: return max(loot[0], loot[1]) #option 1: steal from house 0, and then take # the most we can from house 2 onward valueSteal = loot[0] + houseRobber( loot[2:] ) #option 2: don't steal from house 0, take the # best we can from house 1 onward valueLeave = houseRobber(loot[1:]) return max(valueSteal, valueLeave) |

Running this code passes the first 24 tests, but then times out on test 25.

The problem is for all cases except the base cases, `houseRobber`

calls itself 2 more times. This tells us that we can expect `houseRobber`

to be `O(2^N)`

, where `N`

is the number of houses. To see the calls, and to find a possible remedy, let’s walk through what our code is doing for the input `loot = [4, 1, 2, 7, 5, 3, 1]`

. Each node here represents a call to `houseRobber`

with the input in the box. The boxes have been color-coded, so each different input is represented with a different color.

One of the things that should jump out at you is that we are evaluating the same function *many* times. For example, `houseRobber([5,3,1])`

shown in red is called 5 times! Each time it returns the same value 6 (as robbing the first and the last house gets the most loot from houses with values `[5, 3, 1]`

).

## Improving with memoization

To reduce the amount of redundant work we have to do, one technique is to memorize the answer of each calculation as we do it. This is called memoization, as in “to write down the answer on a memo so we can get it later”. (Actually, memoization comes from the Latin “to be remembered”, but that makes it sound like we should be using the term “memorization” instead!) Basically, the first time we encounter a particular input we will store it in a hash table.

We will not call a helper function for two reasons: not to pollute the global namespace with our previously memoized answers, and because we need to convert `loot`

to a tuple (we cannot use lists as keys to a hash table).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# memoized version of house robber def _houseRobberRecursive( loot, memo_ans ): # have we worked it out already? if loot in memo_ans: return memo_ans[loot] # No? Is it a base case? if len(loot) == 1: memo_ans[loot] = loot[0] if len(loot) == 2: memo_ans[loot] = max(loot) #option 1: steal from house 0, and then take # the most we can from house 2 onward valueSteal = loot[0] + _houseRobberRecursive( loot[2:], memo_ans ) #option 2: don't steal from house 0, take the # best we can from house 1 onward valueLeave = _houseRobberRecursive(loot[1:],memo_ans) # store the best answer memo_ans[loot] = max(valueSteal, valueLeave) return memo_ans[loot] def houseRobber(loot): # our place to store answers memo_ans = { (): 0} new_loot = tuple(loot) return _houseRobberRecursive(new_loot, memo_ans) |

When we run this version, it passes all the tests. We can show the tree of calls to `_houseRobberRecursive`

for this new variation. Note there are many fewer calls, as we are able to reuse anything we have already calculated. (It is important to note the left branch of each note is executed first, because of the order we evaluated `valueSteal`

and `valueLeave`

in `_houseRobberRecursive`

).

## Dynamic programming solution

We already have a solution, but it’s a little messy. We created a helper function to keep our hash table `memo_ans`

outside of the global namespace, because it would be bad if someone else had also written a function that used `memo_ans`

to store their results.

Notice that memoization started with the full list `[4, 1,2, 7, 5, 3, 1]`

and broke it down to smaller and smaller cases. This is called a *top-down* approach. Our next approach will be a *bottom-up* approach, where we start from the small cases and work up to the final solution.

We will introduce an array `steal[i]`

, where `steal[i]`

is the best we can do if we are only allowed to steal from the last `i+1`

houses. If `loot = [4, 1, 2, 7, 3, 1]`

then

`steal[0] = 1`

(if we can only steal from the last house, then the best we can do is taking the last house’s loot)`steal[1] = 3`

(we can either steal 3 or 1; 3 is clearly better)`steal[2] = 8`

(given`[7,3,1]`

stealing`7`

and`1`

is clearly more than just stealing`3`

).`steal[3] = 8`

(best we can do from`[2,7,3,1]`

)- etc.

The answer we actually want is the last element of the `steal`

array.

Remember our magic step for this problem? It was when deciding whether to steal from house `i`

, all we had to do was compare `loot[i] + (most you could steal from house i+2 on)`

and `(most your could steal from house i+1 on)`

. But note that `steal[i]`

tells us the best we can do from the last `i`

houses. This suggests we can find `steal[i]`

using the following technique:

1 2 3 |
# we are trying to decide whether to rob house with loot[-i-1] or not steal[i] = max( loot[-i-1] + steal[i - 2], steal[i-1] ) |

This won’t give us `steal[0]`

or `steal[1]`

, but these are our base cases. Note how much simpler our code becomes:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
# a dynamic programming solution def houseRobber(loot): if len(loot) == 0: return 0 if len(loot) == 1: return loot[0] # go from the end back to the beginning loot.reverse() # the base cases: take everything in the only house, or # rob the house with more valuables steal = [loot[0], max(loot[0],loot[1])] for currValue in loot[2:]: # steal[-2] and steal[-1] are second-to-last and last # elements of steal take = currValue + steal[-2] leave = steal[-1] steal.append(max(take,leave)) return steal[-1] |

This is much tidier, but we can reduce this code even more. Notice that `steal[i]`

depends only on the current value of the loot and the *last two* values of `steal`

. This means we don’t need to keep an array `steal`

. Instead, we just need to keep track of the last two entries.

**Warning:** At the moment, we are still going to accomplish our goal of finding the maximum value that our robber could take. If you wanted to be able to produce a list of houses for the robber to pilfer to achieve the maximum, the `steal`

array is incredibly useful. There is a “backtracking” algorithm to reconstruct which houses the robber should steal from. The optimized version below reduces the space complexity of our solution from `O(N)`

to `O(1)`

, but at the cost of being able to efficiently reconstruct the list of houses that have been hit.

Our new code is:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
def houseRobber(loot): if len(loot) == 0: return 0 if len(loot) == 1: return loot[0] # go from the end back to the beginning loot.reverse() # the base cases: take everything in the only house, or # rob the house with more valuables oldBest, newBest = loot[0], max(loot[0],loot[1]) for currValue in loot[2:]: # steal[-2] and steal[-1] are second-to-last and last # elements of steal take = currValue + oldBest # oldBest is the same as leaving most recent house oldBest = newBest newBest = max(take,oldBest) return newBest |

So far we have implemented the bottom-up technique literally. We have made our way from the “end of the street” and worked backward. However, all that matters in this problem are which houses are next to each other. There isn’t a reason to reverse the houses. We could consider `steal[i]`

as being the most we could steal from the first `i`

houses (instead of the last `i`

houses). The only reason we did it that way is it’s a little easier to conceptualize “running out of houses” at the end of the list.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
def houseRobber(loot): if len(loot) == 0: return 0 if len(loot) == 1: return loot[0] # the base cases: take everything in the only house, or # rob the house with more valuables oldBest, newBest = loot[0], max(loot[0],loot[1]) for currValue in loot[2:]: # steal[-2] and steal[-1] are second-to-last and last # elements of steal take = currValue + oldBest # oldBest is the same as leaving most recent house oldBest = newBest newBest = max(take,oldBest) return newBest |

We can make our problem look a little more like a standard problem with the following observation: if we initialize `oldBest`

and `newBest`

to zero, and go through *every* house, then the first pass through the loop sets `oldBest`

and `newBest`

to the correct value. This simplifies our base cases and makes the problem more familiar:

1 2 3 4 5 6 7 8 9 10 |
# eliminate bases cases and simplify def houseRobber(loot): oldBest, newBest = 0,0 # go through every house for currValue in loot: take = currValue + oldBest oldBest = newBest newBest = max(take, oldBest) return newBest |

## Similar problems

This problem is a *recursively defined series* in disguise. This is a series where you calculate the next value using the previous values. One of the most famous examples is the Fibonacci numbers:

1 2 |
0, 1, 1, 2, 3, 5, 8, 13, ... |

where the first two numbers are `0`

and `1`

. After the first two numbers, we get the next number by summing the previous two numbers in the sequence. For example, the seventh number in the sequence is 8 because `5 + 3 = 8`

. The mathematical expression for the Fibonacci numbers `F[n]`

is given by

and where `F[0] = 0`

and `F[1] = 1`

. This definition leads to a recursive function call:

1 2 3 4 5 6 7 |
# Warning: this function is O(2^n) def fib(n): "Returns the nth Fibonacci number" if n == 0 or n == 1: return n return fib(n - 1) + fib(n-2) |

Because we see each call to `fib(n)`

(except the base cases `n=0`

and `n=1`

) call `fib`

two more times, we are not surprised to find an `O(2^n)`

running time. We can memoize this function (and this is good practice!), but we can also write an iterative or *dynamic programming* solution:

1 2 3 4 5 6 7 8 9 10 |
# This is O(n) def fib(n): "Returns the nth Fibonacci number in reasonable time" if n == 0 or n == 1: return n old, new = 0,1 for _ in range(n-1): old, new = new, old + new return new |

Note how similar the program is to `houseRobber`

. Many problems that involve making a choice to explore two different paths, such as rob house `i`

or not, will given rise to these recursive sequences. This is a good pattern to know!

The overall approach:

- Usually we are iterating through our problem, and have to decide whether or not to include the current element. In this case our decision was whether or not to rob a house, but in other instances it might be whether or not to pack a certain item, or whether we use a road to get to our destination.
- Start by relating this problem to “smaller” instances of the problem. If it helps, write a recursive solution first (although usually these will have bad run times). Usually these smaller instances are related to the different possible choices you could have made. In this case, the smaller instances were “making the best value from the remaining houses”.
- Look at how many of the “smaller” instances you have to use to solve the next instance. In this case, we only used the last two instances. This can help you write the solution as an iterative solution.

## Tell us…

Have you ever gotten a question like this in a technical interview? What strategy did you take to solve it? Let us know on the CodeFights forum!