Solving the Leetcode “Container with Most Water” problem in Javascript

A few years ago I went with a friend to an amusement park, and he challenged me to go on a ride with him called the Ripcord. If you don’t know what this ride is, they attach you to a harness, haul you up between three towers of scaffolding, then they drop you. It just seemed so doable until I was standing at the base of those towers in a harness, looking straight up. And honestly, that’s how some leetcode questions hard. The title says, “Container With the Most Water” and you think “Wow, that sounds so doable.” Then you open it and it just seems so intimidating. But that day, I got hauled 180 feet into the air, and dropped. As terrifying as it was before I did it, afterward I realized it wasn’t nearly as intimidating as it looked. This holds true for this leetcode question, and I’m here to walk you through it.

The first challenge for me with any leetcode question is understanding the actual problem, and that’s where a lot of the intimidation comes from at first. So let’s take a look at the instructions for the leetcode problem Container with Most Water. We’ll be doing this problem in Javascript just as a heads up.

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.

Now maybe you read this and thought, “Yeah, that totally makes sense because I’m a smart intellectual.” And if so, dang. You are a smart intellectual. But I was sitting over here thinking, “Yup. Those are all words, and I can read them all.”

This was my reaction to reading the instructions for this problem for the first time.

So it took me a few minutes of reading, and rereading the instructions, and comparing them to the examples before I understood the actual problem. If you are more like me, let’s talk about what our actual goal is here.

If we look at example 1, it will help us better understand what we are looking for. In more plain words, we’re given an array of numbers, and those numbers represent bars/barriers/walls, (however you need to think of it) that you could pour water into and it would get trapped between them.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Here are a few important things to remember when we are taking on this challenge.

1. This is a 2-dimensional grid, we aren’t worried about the depth of the space
2. We can’t simply select the two tallest bars, because the space between the bars will impact how much water can be held.
3. Likewise we can’t select the two furthest bars, because the height of the bars will impact how much water can be held.
4. A real key important fact here. It’s unlikely we’ll find 2 bars of the same height, and in that circumstance, the smaller height bar will dictate the amount of water being held.

Keep these things in mind as we go forward. When I first approached this, it honestly felt a bit overwhelming. There was so much I needed to do and factor in, the varying heights, how to find the largest area, how to do the calculation, and on top of it, I wanted to get that O(n) time! My brain was spinning.

I relate to Lizzie McGuire so much.

We’re going to look for a brute force solution first. And we’re going to break this into steps. The first thing I did, was figure out how to calculate the area. So I literally pulled out a notepad and just wrote out some notes. What I came up with was this.

1. I needed to determine which wall (number in the array) was bigger
2. I needed to figure out the distance between the walls by subtracting their indexes
3. I needed to multiply the value of the smaller wall, by the difference of the indexes

At that point, everything just clicked. I knew how to get the area of two walls, so now all I had to do was compare them to get a brute force solution. So I set up a variable to contain the highest water total, created a double loop, then used the Math.max function in Javascript to run through each possible area, and always save the highest one. Here is what this looks like, and if you don’t understand it, don’t worry I’m still going to walk through it line by line. One thing to notice is that I changed the argument name from height to heights because it made more sense to me since it was taking in multiple values.

var maxArea = function(heights) {
    let highestWater = 0
    for (let i = 0; i < heights.length; i++) {
        for (let j = (i + 1); j < heights.length; j++) {
            const smallerWater = Math.min(heights[i], heights[j])
            const currentWater = (smallerWater * (j-i))
            highestWater = Math.max(currentWater, highestWater)
        }
    }
    return highestWater
}

Line by Line for the brute force solution:

let highestWater = 0

This one is pretty easy. This is a variable I set to hold my highest water. Since all values are non-negative, I felt pretty safe initiating it at zero.

Let’s talk about what this double loop is doing!

for (let i = 0; i < heights.length; i++) {
        for (let j = (i + 1); j < heights.length; j++) {
  }
}

If you are familiar with double loops in javascript, you can skip this ;) But if you don’t quite understand I’m going to walk you through it.

The first loop is going to run while i is less than heights.length, and it initiates at 0. So if there are 5 numbers in the heights array, the loop will run 4 times, because when it hits 5 it will now be equal to heights. So if our input array was [1,8,6,2], and we did a ‘console.log(heights[i])’ it would log 1, 8, 6, 2.

The second loop is similar in that it will also stop when it hits the end of the array length, BUT there is a crucial difference. I’m initiating the j variable as i + 1. The difference that will make is this. Let’s say we were to console log these values, again anticipating an input of [1,8,6,2].

for (let i = 0; i < heights.length; i++) {
    console.log(heights[i])
        for (let j = (i + 1); j < heights.length; j++) {
        console.log(heights[j])
  }
}

Our console would look like this. 1, 8, 6, 2, 8, 6, 2, 6, 2, 2. Does this make sense? If not here is another visual. I’m going to write this again with a (i) or (j) depending on which loop is logging the number. 1(i), 8(j), 6(j), 2(j), 8(i), 6(j), 2(j), 6(i), 2(j), 2(i). I’m essentially working with 2 points, i, and j.

The reason I’m doing it like this is because we only need to check each pair once. We need to know the value of 1 and 8, and the value of 8 and 1 would be exactly the same. Going backwards is the same distance, which bar is taller will still be the same, and the area will still be the same because the distance of the indexes is still the same. This also prevents me from having to write code to recognize when my pointers are at the same index (which could cause bugs in my code).

const smallerWater = Math.min(heights[i], heights[j])

In this line of code I’m using Math.min() which takes two arguments (or you can use the spread operator to spread an array as an argument) and it returns the smallest value. In this vase, I’m using it to assign the smaller index between my i pointer, and my j pointer. So it’s literally picking the smaller wall/bar. As an example, if my input was [1,8,6,2], and i was on index 1, and j was on index 3, smallerWater would be = to 2.

const currentWater = (smallerWater * (j-i))

Then I am calculating what the area of the water is between the bars my points are currently on by multiplying the value of the smaller bar, by the difference of the indexes. Remember that j starts at i+1, so j will ALWAYS be greater than i, so it’s safe to subtract j from i to get the distance. Following the example from the last paragraph, if j = 3, i=1, and smallerWater = 2, our math looks like this. (2 * (3–1)). 3–1 is in the parentheses so we subtract that first and get 2 and now we have (2 * 2), and 2*2 = 4. So currentWater would be = 4.

highestWater = Math.max(currentWater, highestWater)

The last thing I did was assign that variable we set outside the double loop, highestWater to be = to Math.max(currentWater, highestWater). Remember Math.min? Well Math.max literally does exactly the opposite. It returns the higher value. So it compares currentWater to what has been saved previously in highestWater, saves whichever is higher, and continues on with it’s loopy ways.

Now if you enter this solution into leetcode, it will accept it if you hit runcode. But it will not accept it if you hit Submit.

That’s because this is a level MEDIUM question and they expect better optimization than a brute force solution. This means one of the submit tests has a HUGE array that will time out your code. It doesn’t really want to be doing any double loop shenanigans. So now that we’ve figured out the brute force solution. It’s time to optimize.

There are a few things to consider when we look at optimization. First off

1. Only the smaller bar mattered into our math, remember we picked between the larger and smaller bar
2. We don’t actually do anything in that outer loop. It was just a convenient way to check every item against itself.

That being said, I knew the solution was going to be the 2 pointer method. But I did struggle a bit to implement it at first, because it was my first time actually putting it into practice. So, let’s talk about it. What’s the 2 pointer method?

Well really, it’s just using 2 pointers in a single loop and moving them through an array. Most frequently you’ll see this though. One pointer on the left, one pointer on the right, and they meet somewhere in the middle. This is often a great method for getting yourself out of a nested loop. Now keep in mind, only the smaller value matters when we are comparing these pointers, that makes it easier to decide which to move.

So let’s take a look at, and go line by line on the optimized solution.

var maxArea = function(heights) {
    if (heights.length <= 1) return 0
    let highestWater = 0;
    
    let p1 = 0
    let p2 = heights.length-1
    
    while (p1 < p2) {
        const smallerWater = Math.min(heights[p1], heights[p2]);
        const width = p2 - p1;
        const currentWater = smallerWater * width;
        highestWater = Math.max(highestWater, currentWater);
        heights[p1] <= heights[p2] ? p1++ : p2-- 
        
    }
    return highestWater
}

So first we’ll start with

if (heights.length <= 1) return 0

If the length of the heights array is less than or equal to 1, then there is nothing to multiply, so we can safely return 0.

let highestWater = 0;
    
let p1 = 0
let p2 = heights.length-1

Next we are setting some initial variables. As before, highestWater = 0. Then I set variables for my pointers, you could name these left and right, i and j, or p1 and p2. Whatever makes the most sense to you. The left pointer will start at 0, and the right pointer will start at the length of the array minus 1 because remember, arrays start at 0, so if there are 5 elements in an array, those indexes are 0, 1, 2, 3, 4, which means we need our second pointer to start at heights.length-1 (or in my example, index 4).

while (p1 < p2) {
}

This is pretty simple. A while loop. While pointer 1 is less than pointer 2. If they hit each other, it stops.

const smallerWater = Math.min(heights[p1], heights[p2]);

Does this bit of code look familiar? It should. It’s pretty much exactly the same as last time, except this time, it’s using the p1 and p2 variables to call the indexes.

const width = p2 - p1;
const currentWater = smallerWater * width;

This one is almost exactly the same but for readability I saved width to a variable of it’s own. But currentWater is still = to smallerWater * (p2-p1). So nothing has changed.

highestWater = Math.max(highestWater, currentWater);

Exactly the same. Is this blowing your mind? Here is the only difference.

heights[p1] <= heights[p2] ? p1++ : p2--

So instead of having that double loop checking every value, here I’m using a ternary conditional to check if the first pointer’s value is less than or equal to the second pointer’s value. If it is, it increments the first pointer, and if not, it decrements the second pointer, moving them closer together. This works because the two major factors of our equation are width, and the smaller height of the column. Let’s look at an example.

Remember last time we used this as an example: [1,8,6,2]

P1 starts on 1 (index 0)| P2 starts on 2 (index 3)

It will calculate the max area. The width is 4, and the smaller column is 1. 1*3 is 3. This becomes our currentWater. Our highestWater is currently 0, so when it calculates the max, 3 becomes our highestWater.

Then it checks if 1 ≤= 2 ? 1 is in fact less than 2. So it increments the pointer on 1.

Now P1 is on 8 (index 1)| P2 is still on 2 (index 3)

The width of these is 2 (3–1), we take the smaller number (2) and multiply that by the width (2) and we have 4, which becomes the currentWater. The currentWater is greater than the highestWater so highestWater also becomes 4.

8 ≤= 2? nope. This means we decrement the pointer that was on 2.

So now our pointers are P1 is on 8 (index 1) | P2 is on 6 (index 2)

The width is 2–1 (1). We take the smaller number (8 vs 6, so we need 6), and multiply that by the width (1). 6x1 is 6, which becomes the currentWater. 6 is greater than 4 so it also becomes the highestWater.

Because our pointers are currently on 1 and 2, the next move of a pointer will make them equal and will break us out of our loop.

And this is the easy and most satisfying part. At this point, all we have to do is return our answer

return highestWater

And have the satisfaction of knowing that:

Runtime: 76 ms, faster than 98.21% of JavaScript online submissions for Container With Most Water.
Memory Usage: 48.3 MB, less than 28.61% of JavaScript online submissions for Container With Most Water.

With all of these leetcode problems, just try to take them in small steps. Don’t try to get a perfect solution right off the bat. Sometimes getting something small, like figuring out how to calculate the area can be the key you need to unlocking the rest of the problem for yourself.

And the next time you are staring at an intimidating leetcode question, or possibly even an amusement park ride, I want you to remember this.

You can do it. Danny Trejo believes in you.