Algorithms 101: Container with most water in JavaScript

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

Photo by Doğukan Şahin on Unsplash

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

since the left wall is higher, keep it; decrement j to check out the next right wall…

Here’s what that looks like in code.

if left wall is lower than right wall, select a new left wall; otherwise select a new right wall …

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

JavaScript in Plain English

Learn the web's most important programming language.

Joan Indiana Lyness

Written by

Full-stack developer, Ruby, Rails, JavaScript, i love! React. My portfolio: https://joan-indiana-lyness.com/projects

JavaScript in Plain English

Learn the web's most important programming language.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade