Container With Most Water (Reservoir Problem)

Solution for this lesson: LeetCode 11 - Container With Most Water (Medium)

Given $n$ non-negative integers $a_1, a_2, \dots, a_n$, where each represents a point $(i, a_i)$ on the coordinate plane. Draw $n$ vertical lines such that the two endpoints of line $i$ are $(i, a_i)$ and $(i, 0)$. Find two lines that, together with the $x$-axis, form a container that holds the most water.

Note: You may not tilt the container, and $n$ is at least 2.

The vertical lines in the figure represent the input array [3,8,6,2,5,4,8,3,7]. In this case, the maximum amount of water the container can hold (shown in blue) is 49.

This problem has a very low number on LeetCode, so I’m sure you’ve all seen it before. The problem statement is easy to understand, but solving it is not so straightforward — especially coming up with an $O(n)$ time complexity solution. Even after seeing the answer and learning how the $O(n)$ approach works, you might not be able to prove its correctness.

What many people haven’t noticed is that this problem is actually extremely similar to Problem 167 - Two Sum II. The two problems look completely unrelated from their descriptions, but their solutions and correctness proofs are nearly identical. In the previous article, LeetCode Problem Deep Dive Lesson 4, the example I used was the Two Sum II problem, and this Container With Most Water problem was listed as a related exercise.

This lesson’s solution is closely related to the Two Sum II solution. If you’ve forgotten what the Two Sum II problem is or how to solve it, I strongly recommend reading the explanation in the previous article first:

LeetCode Problem Deep Dive | 04 Solving Two Sum with Two Pointers: Reducing the Search Space

Solution

Reverse-Engineering the Approach from Complexity

The brute force solution for this problem is easy to come up with — just enumerate all pairs of pillars and compute the water area for each combination. The brute force time complexity is $O(n^2)$.

Obviously, the brute force approach won’t be the final answer. We need to do better than $O(n^2)$, which basically means either $O(n \log n)$ or $O(n)$.

If it were $O(n \log n)$, we’d likely use divide and conquer. But divide and conquer requires splitting the problem, and many pillar pairs span across the left and right halves after splitting, making them hard to handle. So divide and conquer doesn’t work well here.

If it were $O(n)$, our first thought might be dynamic programming. But the subproblems don’t seem to have meaningful relationships. The water area depends only on the heights of the two chosen pillars and has nothing to do with the other pillars. Since we can’t find relationships between subproblems, dynamic programming isn’t a good fit either.

Seems like we’re stuck? No worries — we still have the two-pointer technique, which we just covered in the previous article.

Two-Pointer Solution

Similar to Two Sum II, this problem has a search space of $O(n^2)$ size. The brute force approach examines one case in the search space at a time, naturally resulting in $O(n^2)$ time complexity. What we want is a method that eliminates multiple cases at once, thereby reducing the time complexity.

To start, let’s consider the water area formed by the two pillars that are farthest apart. The water width is the distance between the two pillars, $d = 8$; the water height is determined by the shorter of the two pillars, which is the left pillar with height $h = 3$. The water area is $3 \times 8 = 24$.

If we fix one pillar and move the other, how does the water area change? With a bit of thought, we can see:

• The current pillars are at the two extreme ends, so the water width $d$ is at its maximum. Any other combination will have a smaller width.
• The left pillar is shorter, setting the water height to 3. If we move the left pillar, the new water height is uncertain, but it will never exceed the right pillar’s height of 7.
• If we move the right pillar, the new water height will never exceed the left pillar’s height of 3 — meaning it won’t exceed the current water height.

From this, we can see that if we fix the left pillar and move the right pillar, the water height will never increase while the width will definitely decrease, so the water area will certainly decrease. At this point, any combination of the left pillar with any other pillar can be ruled out. In other words, we can eliminate the left pillar entirely.

Eliminating the left pillar corresponds to moving the pointer one position to the right in the two-pointer code. In terms of the search space, it means trimming an entire row, as shown in the figure below.

As you can see, the way the search space is trimmed is exactly the same shape as in the Two Sum II problem (I actually just reused the diagrams from the previous article). If you understood Two Sum II, you’ll instantly understand this problem.

By the same logic, if the right pillar is shorter, we can eliminate the right pillar and trim a column of the search space, as shown below.

This way, after $n$ steps, we can eliminate the entire search space and check all possibilities.

And so, we arrive at the following two-pointer code:

public int maxArea(int[] height) {
    int res = 0;
    int i = 0;
    int j = height.length - 1;
    while (i < j) {
        int area = (j - i) * Math.min(height[i], height[j]);
        res = Math.max(res, area);
        if (height[i] < height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

Summary

Honestly, very few people can come up with this elegant two-pointer solution the first time they encounter this problem. So the process of improving through practice inevitably involves “memorizing solutions.” But at the same time, we should be good at generalizing and summarizing, because rote memorization is hard work — only by truly understanding the underlying ideas can we learn faster and retain better.

Take Problem 167’s Two Sum II and this problem, for example. Both use the same two-pointer approach and look very similar in code, but why are they so similar? In reality, both problems share the same principle of reducing the search space, and their problem-solving approaches are actually identical. If you can see this connection, you’re not far from being able to apply these ideas to new problems.