Container with most water

So I recently came across the Container With Most Water, a LeetCode Medium leveled problem, it is a classic and insightful question.

Let’s understand and decode this problem step-by-step and then explore different approaches.

Problem statement:

Given an integer array height of length n, we interpret it as n vertical lines, where each line is drawn from (i, 0) to (i, height[i]). You need to find two lines that, together with the x-axis, form a container that holds the most water.

Important points:

• Water is considered in 2D here.
• The container cannot be slanted — it must be vertical (aligned with the y-axis).
• The width of the container = distance between the two lines = j - i
• The height (further referred to as ht) of the container = min(height[i], height[j]), because water cannot rise above the shorter wall.
• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Let’s simplify the problem:

Let’s take an example to simplify the understanding process:

height = [1, 4, 9, 2, 6, 8, 10, 7, 5]
If we choose the first and second index (2 and 7):

• Think of the two vertical lines at indices i and j as the walls of a container, and the space between them as the area where water can be stored. The height of water in this container is limited by the shorter wall.
• Let’s say:
• height[i] = 9(left wall)
• height[j] = 7(right wall)
• Width = j - i = 5

So the container looks something like this from the side:

Image depicting the mentioned example.

Even though the right wall is tall (9 units), the left wall is only 9 unit high. So when water is poured between them, it fills up only to the height of the shorter wall (7 unit). Any extra water above that on the taller wall just spills over, it doesn’t get trapped.

Get Eshita Chokhani’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

In other words, water doesn’t “lean” on one side, it needs both sides to hold it in. So, the effective height of the container is the shorter of the two walls, which is why we use:

• Area (Water) = 7(ht) * 5(width) = 35

We need to compute this area for every possible pair of lines and return the maximum value.

Brute force approach (Two loops):

Logic:

We use two nested loops to try all possible pairs of lines and compute the container area each time. We keep track of the maximum area found so far.

Code:

Brute force approach

Time complexity:

• O(n²) because we check every possible pair.

Why is this not ideal ?

Given the constraints 2 ≤ n ≤ 10⁵, this would result in ~10¹⁰ operations, but our goal should be around 10⁸ operations for performance, making this approach inefficient.

Optimal two-pointer approach:

To make this solution efficient, we can use a greedy two-pointer technique.

Steps:

1. Place two pointers
2. start = 0 (left end)
3. end = height.size() - 1 (right end)
4. Initialize maxWaterFin = 0
5. Loop until start < end:
6. width = end - start
7. ht = min(height[start], height[end])
8. area = width * ht
9. Update maxWaterFin if this area is greater.

Pointer movement logic:

Now comes the key insight, which pointer do we move?

• We always move the pointer with the smaller height.
• Why? Because moving the taller line cannot help us get more water — the limiting factor is the shorter line.
• Moving the shorter line might lead to finding a taller one, which could increase the minimum height and thus potentially a greater area.

Code:

Two pointer approach

Time & space complexity:

• Time Complexity: O(n) → Every element is considered at most once.
• Space Complexity: O(1) → We only use constant space.

Why not move the max value?

Let’s think through a few hypothetical cases when trying to move based on the taller value:

Case 1:

If the next height is less than the previous, and min remains same, area doesn’t increase.

Case 2:

If the next height is equal, the min still remains same, no increase.

Case 3:

If the next height is greater, but min remains same, again, no benefit.

In all three cases, moving the taller value gives us no guarantee of improvement. Hence, we rely only on moving the shorter pointer, which is the only factor limiting the area.

Why not move the min value ?

Consider if the minimum value pointer is moved:

Case 1:

The new value is less than the previous then, the new area is less than the previous one, hence the max amount remains same, not updated.

Case 2:

The new value is equal to the previous, the new area remains same as the previous, the max amount remains same, not updated.

Case 3:

The new value is more than the previous, the new area is more than the previous and hence the max amount also increases, hence the max value is updated.

Hence we come to the conclusion that we move the pointer pointing to the minimum value.

Conclusion

This is one of those problems that really clicked with me. At first glance, it seemed pretty straightforward, just find two lines that trap the most water. But what made it really interesting was how a clever observation could turn a brute-force approach into a much more optimized one.