# Algorithms 101: Container with most water in JavaScript

## Noob v. Algorithms # 20, iterating from the outside in

If you’re a noob like me you may dread the ‘medium’ level algorithms on LeetCode. As it turns out, a few of them are actually easier than the so-called Easy ones. Here’s a gentle introduction to the medium level.

Today’s challenge from Leetcode is to choose the container that holds the most water:

# Let’s talk about volume

The volume of water will be `height x length x depth`

. In our case, depth is the thickness of the container from back to front — we are assuming it does not change. So for this challenge, we are only concerned with `height x length`

.

**Height: **As you can see, the heights vary. In the picture above, we have a container that is 8 units high on one side and 7 high on the other. When we’re making our calculation we have to choose lower one of these heights since the container’s volume is limited by its lowest wall.

**Width**: In the picture above we can see 9 walls. The width of our container is the x-coordinate of the right wall minus the x-coordinate of the left. Since our input data is in the form of an array, we’ll use index numbers instead of x-coordinates to make that calculation.

# From the outside in

Us noobs have a habit of iterating from left to right:

`(for let i = 0; i < array.length; i++)`

or, when we’re feeling daring, from right to left:

`(for let j= array.length = 1; j >= 0 ; j--)`

In this case, we need to do both.

We’re going to start with the outside walls, pick the one that’s lower in height, and multiply by the width (the index of the right wall minus the left wall). We’ll call the result *area*.

Meanwhile, we’re going to set a variable called *max*, with a default value of 0. Each time we calculate area, we’ll compare it to max, and set max equal to the higher of the two values.

So far, our code looks like this:

Let’s unpack that:

On line 3, we’re setting `i`

* *equal to the index of the left wall, starting with `0`

.

On line 4, we’re setting *j* equal to the index of the right wall, starting with the last element of the input array `height.length — 1.`

On lines 5 and 6, we’re declaring variables for max and area. *(Why don’t we set area equal to zero? We could, but we don’t need to. We’re going to calculate area — as you can see on line 9. But we never calculate max — we just set it equal to the higher of two variables, so we need to give it an initial value of 0. )*

On line 11, we’re using JavaScript’s Math.max() to return the highest value that we pass in to it.

On line 8, we’re saying we want to iterate while our left wall, `i`

* *is still on the left side (i.e. less than) our right wall,* *`j`

*.*

# Test Drive — the first loop

Let’s say we have an initial input, `height = [1,8,6,2,5,4,8,3,7]`

In our first loop, `i = 0`

, `j = 8`

(remember, these are indexes, not values).

The wall at `height[i]`

is 1 unit high. The wall at `height[j]`

is 7.

The width is `j — i => 8 — 0 = 8`

.

Area = `height of lower wall * width => 1 x 8 = 8.`

We compare that to our `max`

, which has an initial value of `0`

. Since `area`

is greater than `max`

, we set `max`

equal to `8`

.

Now we’re done with our first loop.

# Which way do we iterate for our second loop?

In our first loop, our left wall was lower than our right wall. Now we want to compare the next combination of two walls. The next combination should include the higher of the two walls we already have, plus the wall next to the shorter wall.

Since our right wall is higher, let’s ‘keep’ it (i.e. let’s not change the value of `j`

, the index of our right wall). Instead, let’s increment `i `

by 1, which means our new left wall is at index 1.

In our first loop, we compared walls at indexes 0 and Now, in our next loop, we’ll be comparing the walls at indexes 1and 8 (the red walls below).

Here’s what that looks like in code.

Then we keep looping until `i`

meets `j`

in the middle.

All together now:

And … it runs pretty fast:

You can see the code execute live here on PythonTutor.com and you can play with it here on repl.it:

https://repl.it/@Joan_IndianaInd/container-with-most-water

Copyright © Joan Indiana Lyness 2019

Next: Algorithms 101, #21, .includes() vs. IndexOf() in JavaScript/ intersection of two arrays.

*In case you missed it: **Algorithms 101, #19, Level Patio in JavaScript*