# Algorithms 101: House Robber in JavaScript

## Noob v. LeetCode, episode 7, array manipulation.

There’s a robber on the loose! He’s done his homework, so he knows the street worth of the valuables for each house on the block. Here’s the description on LeetCode. And here’s the link.

This definitely in the easy category, but this Noob did not find it easy. I worked on this with some friends and in fact none of us found it easy!

My first guess was — well maybe we should add up all the even houses vs. all the odd houses and pick the largest. That strategy would work for the test cases above. Unfortunately, it doesn’t work in a lot of cases.

For example, in this array:

`array = [1, 9, 6, 3, 2, 7, 9]`

The even indexes (array[0], array[2], etc) add up to 18; the odd indexes add up to 19. But if you cherrypick, you can choose both 9s and the 3, for a total of 21.

# So, how do we cherrypick in our code?

The way I did it visually was to look for the largest number, mentally avoid the numbers next to it, then pick the largest number left, etc. This approach didn’t work for us because it considered the largest numbers without considering the numbers next to them. It didn’t take into account an array like this:

`[ 1, 9, 9, 8, 4, 3]`

In this array, we have two nines — but clearly, we are better off choosing the first nine, because that way, we can still choose the 8. So the way to choose between the two large values is to compare them in the context of the values on either side of them.

We thought about choosing the largest numbers, and if there were several of them, choosing the one with the lowest surrounding values. We were having trouble making this approach work until we … reverse-engineered other solutions.

# Reverse Engineering — better than giving up

The solutions we found considered three numbers at a time from the beginning of the array, instead of picking the max values out of the middle of the array. Here’s what we did:

Assuming there are at least two numbers in the array (arrays of only one and two numbers are edge cases we’ll deal with later), we set up a new array, *sorter*, where we can calculate our changing haul.

We start out by adding the first number in the nums array to *sorter*. Then, we consider the second number in the nums array. Since they are adjacent, we can’t choose both; we’ll pick the larger of the two and put it at the end of our sorter.

Here’s what we have so far:

let nums = [1, 5, 9, 4, 2, 20, 3, 7]

var rob = function(nums) { //deal with edge cases here //compare first two numbers of array, pick greater value

let sorter = []

sorter[0] = nums[0]

// => [ 1 ] sorter[1] = Math.max(nums[1], nums[0])

// => [1, 5]}

After evaluating just the first two numbers of the array, we decided house #2 , with a robbable value of 5, was the better choice.

But we want to keep house #1 in mind, in case house #1's value plus the value of the current house (which we have to avoid if we chose house #2), adds up to more than 5.

In the code below, we’re saving our maximum haul if we start with house #1 as *optionA. *We’re saving our maximum haul if we start with house #2 as* optionB.*

Let’s think of the item we’re looping over, *nums[i]* as the *currentHouse*.

When we’re deciding whether to rob *currentHouse*, we need to consider: Is it more valuable to go with our max haul of *optionA*, plus the *currentHouse*, or our other possible max haul of *optionB*, which can’t include *currentHouse*? Then we add the greater of those two values to the end of our *sorter* array:

`for(let i = 2; i < nums.length; i++){`

let optionA = sorter[i-2]

let optionB = sorter[i-1]

let currentHouse = nums[i]

if(option A + currentHouse > optionB){

sorter[i] = optionA {

else {

sorter[i] = optionB

}

Let’s see how this plays out with this array of nums:

` [1, 5, 9, 4, 2, 20, 3, 7]`

Sorter starts out with [ 1, 5]

Now we consider the third house. Do we get more money by robbing house #3 (value 9) and adding it to house #1 (value 1), or should we just stick with house #2 (value 5)? Since 1 + 9, or 10, is greater than 5, we’ll add 10 to the end of *sorter*:

`sorter: [ 1, 5, 10]`

Next, let’s look at house #4. Again, do we get more moola by robbing house #4 (value 4) and adding it to *optionA* (the haul that does NOT include house #3), or should we skip the current house and stick with *optionB* (the haul that does include house #3). Since *optionA* + *currentHouse* (5 + 4) is less than *optionB* (10), let’s put 10, the greater value, at the end of *sorter*.

`sorter [1, 5, 11, 10]`

# Secret Weapon

If you’re having trouble following along fellow noobs, it’s not just you. But — here’s a secret weapon! (Thanks to Cynthia Eddy for pointing this out to me!)

Even if you are not working Python, you can use PythonTutor.com to run code in many languages, and have it step through the code line by line so you can see exactly what is happening. (When you land on the page, click on the ‘visualize your code …’ link,

pick your language, enter your code with input, call the code, and then click ‘visualize execution’.

On the next page, click the ‘forward’ button to step through your code. As you do, it fills in the values from your code.

Below the nums array is at the top; sorter is at the bottom.

Here’s what our code looks like, including an if statement to deal with edge cases:

var rob = function(nums) {

if(nums.length === 1){

return nums[0]

} else if(nums.length === 0){

return 0

}

let sorter = []

sorter[0] = nums[0]

sorter[1] = Math.max(nums[1], nums[0]) for(let i = 2; i < nums.length; i++){

let optionA = sorter[i-2]

let optionB = sorter[i-1]

let currentHouse = nums[i]

if(optionA + currentHouse > optionB){

sorter[i] = optionA + currentHouse

} else {

sorter[i] = optionB

}

}

return sorter[sorter.length-1]

}

# Re-factor!

Thanks to Benjamin Cantlupe (see comments), for his suggestion on fixing this loop. We never need all of the values in our sorter, just the last two. So instead of building out a long array, we can store and update just two values in the sorter, like so:

`for(let i = 2; i < nums.length; i++){`

let optionA = sorter[0]

let optionB = sorter[1]

let currentHouse = nums[i]

sorter[0] = optionB;

sorter[1] = Math.max(optionA + currentHouse, optionB)

}

return sorter[1];

In the code above, after we declare our variables, we update sorter[0] by setting it equal to option B (the current last value in the sorter). Then we update sorter 1 as the greater of *optionA + currentHouse*, or *optionB*, and we do it with the cleaner *Math.max()*.

At the end of the method, we still return the last value in sorter.

Now our whole function looks like this:

var rob = function(nums) {

if(nums.length === 1){

return nums[0]

} else if(nums.length === 0){

return 0

}

let sorter = []

sorter[0] = nums[0]

sorter[1] = Math.max(nums[1], nums[0]) for(let i = 2; i < nums.length; i++){

let optionA = sorter[0]

let optionB = sorter[1]

let currentHouse = nums[i]

sorter[0] = optionB;

sorter[1] = Math.max(optionA + currentHouse, optionB)

}

return sorter[1];

}

More efficient, more readable and it’s still speedy!

*next: Algorithms 101, #8: Best Time to Buy and Sell Stock in JavaScript*

*in case you missed it: **Algorithms 101, #6: convert Roman Numerals to Integers in JavaScript*

*note: technically, a person who steals from a house without confronting anyone is a burglar! not a robber. A robber robs a person, a burglar steals from a place.*

Copyright © Joan Indiana Lyness 2019