Container With Most Water
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 area depends on both factors at once. A wide container with short walls can hold more water than a narrow container with tall walls, or the other way around, so neither width nor height alone decides the answer.
Key Constraints:
2 <= n <= 10^5→ There are about n^2/2, or 5 billion, pairs at the upper bound, so an O(n^2) scan over all pairs is too slow. We need something close to O(n).0 <= height[i] <= 10^4→ The largest possible area is 10^4 * (10^5 - 1), which is below 10^9 and fits in a 32-bit signed integer. No long arithmetic is needed.
Approach 1: Brute Force
Intuition
Check every possible pair of lines, compute the area for each, and keep the largest. There are n*(n-1)/2 pairs, and evaluating all of them is guaranteed to find the answer. This establishes a correct baseline before any optimization.
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.
At n = 10^5 this is around 5 billion pair evaluations, far beyond the time limit. The next approach starts from the widest possible container and discards pairs in bulk instead of measuring each one.
Approach 2: Two Pointers (Optimal)
Intuition
Start with two pointers at the far ends of the array, which gives the maximum possible width. Every move inward costs width, so a later pair can only win by having a taller minimum height.
That determines which pointer to move. The area is limited by the shorter of the two lines. Moving the taller line's pointer shrinks the width while the height stays capped by the shorter line that did not move, so the area can only decrease or stay the same. Moving the shorter line's pointer also costs width, but it can replace the limiting line with a taller one, and that is the only change that can raise the area.
Always moving the pointer at the shorter line is the greedy choice, and it never skips a pair that could be the answer.
Each time a pointer moves, a batch of pairs is discarded without being evaluated. Suppose height[left] <= height[right] and we move left. The pairs we give up are (left, m) for every m strictly between left and right. None of them can beat the pair we measured before moving: each has a smaller width than right - left, and its height is still at most height[left], because the line at left caps the minimum. Every discarded pair is therefore dominated by a pair already evaluated (the symmetric argument covers moving right), so the maximum is never skipped.
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
Loading simulation...
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.