Container With Most Water
Last Updated: March 21, 2026
Understanding the Problem
We're looking at vertical lines on a 2D plane. Each line is positioned at index i with a height of height[i]. If we pick any two lines, they form the sides of a container. The water this container can hold depends on two things: the distance between the two lines (the width), and the shorter of the two lines (the height, since water would overflow past the shorter line).
So for any pair of lines at indices i and j, the area is:
The question is: which pair gives us the maximum area?
The key observation here is that the area depends on both width and height. A wide container with short walls might hold more water than a narrow container with tall walls, or vice versa. We need to find the right balance.
Key Constraints:
2 <= n <= 10^5→ We need O(n log n) or better. An O(n^2) brute force will be too slow.0 <= height[i] <= 10^4→ Heights are non-negative, so we don't need to worry about negative values.
Approach 1: Brute Force
Intuition
The most straightforward approach is to check every possible pair of lines and compute the area for each. We pick the pair that gives the maximum area. There are n*(n-1)/2 pairs, so we try them all.
This is the natural starting point. If someone asked you to find the best container and you had unlimited time, you'd just measure every combination and pick the winner.
Algorithm
- Initialize a variable
maxAreato 0. - For each line at index
ifrom 0 to n-2: - For each line at index
jfrom i+1 to n-1: - Calculate area = min(height[i], height[j]) * (j - i).
- Update
maxAreaif this area is larger. - Return
maxArea.
Example Walkthrough
Code
- Time Complexity: O(n^2). We check every pair of lines. There are n*(n-1)/2 pairs, each taking O(1) to evaluate.
- Space Complexity: O(1). We only use a few variables regardless of input size.
This approach works but is too slow for the given constraints. What if we started with the widest container and strategically narrowed our search, skipping pairs that can't possibly beat our current best?
Approach 2: Two Pointers (Optimal)
Intuition
Here's the key insight: start with two pointers at the far ends of the array. This gives us the maximum possible width. Now, as we move pointers inward, the width decreases. So the only way to find a larger area is to find a taller minimum height.
But which pointer should we move? Think about it this way. The area is limited by the shorter of the two lines. If we move the taller line's pointer inward, the width shrinks and the height can't increase (it's still capped by the shorter line that didn't move). So the area can only decrease or stay the same. There's zero upside.
On the other hand, if we move the shorter line's pointer, we lose width, but we might find a taller line. The height was capped by this shorter line anyway, so replacing it with something taller could increase the area enough to overcome the width loss.
This greedy choice, always moving the pointer at the shorter line, guarantees we never skip a pair that could be the answer.
Say the optimal answer uses lines at indices i and j (where i < j). At some point during our algorithm, one of our pointers will be at i or j. The question is: will both pointers ever be at i and j at the same time?
The answer is yes. Suppose left reaches i first. At that point, right is somewhere to the right of j (or at j). As we move right inward, will it skip past j? Only if height[right] > height[left] at every step, which would mean left moves instead. But left is at i, one of the optimal lines. The key guarantee is that we never move a pointer in a way that skips the optimal pair, because moving the shorter pointer is the only strategy that could lead to improvement.
Algorithm
- Place a left pointer at index 0 and a right pointer at index n-1.
- While left < right:
- Calculate the area using the two lines at left and right.
- Update
maxAreaif this area is larger. - Move the pointer pointing to the shorter line inward (if they're equal, move either one).
- Return
maxArea.
Example Walkthrough
Code
- Time Complexity: O(n). Each pointer moves at most n-1 times total. In each iteration, at least one pointer moves inward, so the loop runs at most n-1 times, with O(1) work per iteration.
- Space Complexity: O(1). We only use a constant number of variables: two pointers and the max area tracker.