In this article, we will solve LeetCode problem #11 — Container With Most Water. We’ll approach the solution iteratively: first we’ll write a brute-force version and then optimize it. The final solution ends up being somewhat different from the explanations on the platform and other resources I’ve seen. I hope this article will help those who, even after reading through explanations of the problem, still aren’t sure they fully understood the solution — and also those who aren’t sure they would have been able to come up with this solution during an interview.

Problem Statement Link to heading

We have n vertical lines: the i-th line is located at x-coordinate i and has a height of h[i]. Suppose we choose two lines at coordinates (i.e., with indices) i and j, with i < j. Imagine water being poured between them from above. Then, the water will rise to a maximum level of min(h[i], h[j]): any extra water would spill over the shorter line. The area of the water held will be: width * height = (j - i) * min(h[i], h[j]). The task is to find the maximum area of water that can be held between any pair of lines.

Constraints: 2 ≤ n ≤ 10^5, 0 ≤ h[i] ≤ 10^4.

A Small Digression Link to heading

Recently, I was approached with a question about this problem. After reading through the solution, the person felt they still didn’t fully understand the proposed approach, and also couldn’t figure out how one could have come up with this solution during an interview. I read the explanation myself and felt that the correctness of the solution isn’t all that easy to grasp, despite its concise implementation. All the explanations from LeetCode users that I saw, and the solutions described on other websites, were essentially just rephrasings of the “official” solution.

In order to explain how this problem can be solved without a “eureka” moment — a sudden realization of the final idea — I tried to solve it in a slightly different way. In this article, I describe what I ended up with.

We’ll write a brute-force version and iteratively improve it.

Continuing with a faithful translation of the next section:

Official Solution Link to heading

In the official solution, it is suggested to use the two-pointer method: l = 0, r = n - 1. Let the answer be stored in a variable ans, initially set to 0. As long as the two pointers have not met, do the following:

  1. Attempt to update the answer: ans = max(ans, (r - l) * min(heights[l], heights[r]))

  2. Move the pointer that is pointing to the shorter line:

    if heights[l] < heights[r] {
    l++
} else {
    r--
}

  3. The final answer will be stored in ans.

I’ve read other explanations of this problem, including those by LeetCode users and various breakdowns on the internet, and came to the conclusion that all of them use exactly the same method to solve the problem.

I’m not surprised that after reading such explanations, people might still have questions and feel unsure whether they really understood the problem. Moreover, I suspect that a large portion of those who solved the problem using this exact method don’t actually fully understand why it works — something supported by a small informal poll I did.

Here are some questions one could ask themselves to verify whether they truly understand the solution:

  • Why is it true that, using this algorithm, we have either already passed the best possible pair of lines or will encounter it later?
  • In other words, why are we confident that for the optimal pair L and R, there will be a moment when l == L and r == R?
  • Why is it impossible for the algorithm to “accidentally” skip one of the lines that forms the optimal pair?

Indeed, if one simply reads that the topic of the problem is “two pointers,” it’s easy enough to arrive at the solution this way:

This is a two-pointer problem. Therefore, we place one pointer at the first line and the other at the last. We try to update the result. Now we need to move one of the pointers. Should we move the one pointing to the taller line? Of course not. So, we move the one pointing to the shorter line. Repeat until the pointers meet. Submit — all tests passed. Problem solved.

Let’s now try to solve the problem step by step, starting from a simple brute-force approach and ending with the correct solution.

Iterative Approach Link to heading

Let’s suppose we don’t know how to approach this problem. Then we can try writing a brute-force solution.

ans := 0
for l := 0; l < n - 1; l++ {
    for r := l + 1; r < n; r++ {
        ans = max(ans, (r - l) * min(heights[l], heights[r]))
    }
}

The time complexity of this solution is O(n^2). Hmm… this doesn’t fit within the problem’s constraints. It doesn’t lead to any new ideas either. Let’s try a slightly different approach. Let’s iterate over the height h of the water that could be held between the “best” pair of lines. That is, go through all possible values from 0 to the maximum allowed height: 10^4 = 10000.

Now, for each possible water height, we need to find a pair of lines that can hold water of at least that height. To maximize the area, we’re interested in two lines that are as far apart as possible. To find such a pair, we place pointer l at the leftmost line (index 0), and pointer r at the rightmost (index n - 1). These are the most distant lines possible. Now we skip all lines from the left and right that are too short to hold water of height h, i.e., all lines with height less than h. The resulting pair of pointers l and r are the furthest apart lines that can hold water of height h.

ans := 0
for h := 1; h <= 10000; h++ {
	l, r := 0, n - 1
	for ; l < r && heights[l] < h; l++ {}
	for ; l < r && heights[r] < h; r-- {}
	ans = max(ans, (r - l) * h)
}

The complexity of this solution is O(H * n), where H is the maximum possible height, which according to the constraints is 10^4.

We can make the following observation: the water height h increases monotonically as we iterate. Therefore, if the lines l and r can contain water of height h, then for height h + 1, only either the same pair l and r, or some pair within the segment [l; r], can possibly work. We skipped lines 0..l-1 and r+1..n-1 because they couldn’t hold even the smaller height h, which means they definitely won’t be suitable for a greater height either.

This observation allows us to make the following optimization: we don’t need to reset l and r to 0 and n-1 every time — instead, we can update them for each new height h:

ans := 0
l, r := 0, n - 1
for h := 1; h <= 10000; h++ {
	for ; l < r && heights[l] < h; l++ {}
	for ; l < r && heights[r] < h; r-- {}
	ans = max(ans, (r - l) * h)
}

This solution has complexity O(H + n), where H is the maximum possible height (≤ 10^4 per constraints). This version successfully passes all LeetCode tests, although it’s not optimal due to the relatively weak height constraint. We’ll return to that point a bit later, but for now, imagine the possible range of heights is much larger — say, 0 ≤ h ≤ 10^12. Now our solution becomes slow and fails the time limit. Let’s look for more optimizations.

Suppose on some iteration over h, we have pointers l and r. We can make the following observation: nothing changes during the iterations of h until h becomes greater than min(h[l], h[r]), after which one or both pointers will move, because this height is bigger than containers l and/or r might store. So we don’t need to iterate over all values of h; instead, we can “jump” over the uninteresting ones:

ans := int64(0)
l, r := 0, len(height) - 1
h := 0
for l < r {
	h = min(height[l], height[r])
	ans = max(ans, int64(r - l) * int64(h))
	for ; l < r && height[l] <= h; l++ {}
	for ; l < r && height[r] <= h; r-- {}
}

int64 isn’t necessary in the original problem — it’s only used here to support our larger height range by avoiding overflow when multiplying.

At each iteration we:

  • choose a water level height h such that it is the maximum possible for the pair of containers l, r;
  • try to improve the answer;
  • we have processed the height h, so to move to a greater height in the next iteration, we skip all columns with height less than or equal to h.

Now the time complexity no longer depends on the height range — we’ve eliminated H from the complexity. The resulting solution runs in O(n), which is the best possible asymptotic complexity for this problem, since we need to examine each element of the input at least once.

Let’s recap the steps we took:

  • Wrote a brute-force solution over all pairs of lines;
  • Tried to improve it — and failed;
  • Wrote a different brute-force solution, iterating over water height instead;
  • Noticed a property and used it to optimize;
  • Noticed another property and used it to improve the asymptotic complexity;
  • Arrived at the best possible complexity.

In some problems where it’s unclear how to proceed, brute-force and successive optimizations can lead you to the correct solution.

Continuing with the next section:

Comparison of Solutions Link to heading

Let’s implement the solution from the editorial:

ans := 0
l, r := 0, n - 1
for l < r {
	h := min(heights[l], heights[r])
	ans = max(ans, (r - l) * h)
	
	if heights[l] < heights[r] {
		l++
	} else {
		r--
	}
}

It’s easy to notice the similarity between our solution and the one found in the explanations. Just like in our version, the line with the smaller height will be discarded before the taller one. The difference lies in the fact that in our version, internal loops allow us to skip more pairs that are guaranteed not to improve the answer, while this version checks a larger number of pairs — even if some of them clearly won’t improve the result. In other words, here there is no monotonically increasing sequence of possible water heights h.

It’s worth noting that the pointer movement code here may look slightly simpler, but is it easier to understand why it works correctly? I’d say no. In none of the explanations I’ve seen was there any mention of the redundancy of some of the checked line pairs, or the possibility of maintaining a monotonically increasing sequence of candidate water heights.

What’s Wrong with LeetCode Link to heading

This problem is number 11 out of several thousand on the platform. You’d think that, being so early in the list, it would be well-tested and come with well-designed constraints and test cases. However, a solution that uses brute-force over all possible water heights — which is not the optimal approach for this problem — still passes all the tests.

Someone who solves it using that brute-force method might stop there, never reaching the approach that the problem’s authors likely intended.

Most likely, the height constraint of 10^4 exists because it doesn’t cause an integer overflow when multiplying the maximum height by the maximum possible distance between lines (10^5). But that doesn’t change the fact that the constraints and test cases could have been stricter.

Even within the given problem constraints, the platform sometimes has issues with weak test cases. The problem likely lies in the platform prioritizing the size of the problem archive over the careful preparation of each individual problem.

So what should you do about this? On LeetCode — and generally — even after successfully submitting a solution, it’s worth asking yourself:

Can I solve this problem with better asymptotic complexity?