Container With Most Water (LeetCode #11)

Image by Jonathan Chng on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Maximum Product Subarray.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Container With Most Water problem, you’re in the right spot.

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.

It’s okay if this one has been giving you a hard time. Let’s get right into it so you can get your solution.

Initial Setup 👷🏻‍♂️

The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):

1. We’ll be given a list of integers height
2. Each of these integers represents a height of a side of a potential container (e.g. 4 would indicate a height of 4)
3. We need to find two lines (or sides) of a potential container that generate a maximum area that holds the most water
4. We should return the maximum area of stored water of any containers can hold

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

I think this is enough for us to get started. Let’s get into it!

Variable Setup 💯

It turns out that the key to solving this problem is to use the two pointer technique where we track values from both the right and left sides.

We also should track the maximum total area we’ve seen so far.

This is what that looks like in code form:

As you can see, we initially set our max_area to 0. We should also initialize our left pointer to the 0 index and our left pointer to the end of the length of the height list.

With this out of the way, let’s dive into our loop!

Building Out Our Loop 🔁

Since we’re using two pointers, we’ll probably want to iterate as long as our left pointer is < than our right pointer. This is a common pattern for the two-pointer technique.

The next thing we want to do is to find the smallest side between the left and right pointers.

For instance, say you have this list:

height = [4, 2, 5, 8, 1]

If you were just starting out and our pointer indices were left = 0 and right = len(height) — 1, you’d be comparing the values at those indices of 4 and 1. Out of these two, you’d want to use 1. This is because a theoretical container with those two values as the heights of its walls could not use 4 as the height. Water would spill over on the 1 wall side.

Once we get our smallest wall side, we need to calculate the area of the current container. You might remember that the equation for the area of a rectangle is area = height * length. We already know the height (since we have calculated the smallest height already), so now we just need to figure out the length.

We can get that by subtracting the left side pointer from the right one.

Here’s what this looks like in code form:

Now we have the current area. If this value is greater than the max_area variable we have at the start of our function, we should update max_area to be this new value.

After that, we need to move our pointers. We can do this easily by comparing the values at left and right. If height[left] >= height[right], we can move the right pointer down. Otherwise, we can move the left pointer up.

Here’s what this looks like in code:

Finally (as you can see at the end of the code above), we should return the max_area value.

Boom. We’re done.

This algorithm runs in O(n) time complexity (since we’re only visiting each number once as we iterate through the list) and with O(1) time complexity (since we use a static number of variables no matter how long the height list is).

Conclusion

Great job making it through this one! 🔥

Hopefully you feel much more confident approaching problems like this now.

Keep an eye out for the rest of these Blind 75 coding challenges articles from me. I’m going to be solving them and publishing as I go.

Also, feel free to reach out to me on any of the links below if you want to talk about coding, cool tech, or anything else (I really, really like book recommendations).

Thanks for reading!

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)