Algorithm

Container With Most Water

Two Pointer Pattern

Container With Most Water

You are given an integer array height of length n. Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store.

CONSTRAINTS
  • n == height.length
  • 2 <= n <= 10⁵
  • 0 <= height[i] <= 10^4
EXAMPLE 1
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
The max area is formed by the vertical lines at index 1 and 8.
EXAMPLE 2
Input: height = [1,1]
Output: 1
With only two lines, the only possible container has width 1 and height 1.
Is it possible for the input array to have zero heights?
Yes, heights can be zero, which would result in zero area for that container.
Should I return the indices of the bars or the maximum area?
You only need to return the maximum area found.

Finding the maximum volume of water a container can hold is fundamentally a challenge of balancing width against height. Since the container's volume is limited by its shortest wall, we need a strategy that effectively navigates the trade-offs between the distance between walls and their individual heights.

The Exhaustive Search (O(N²))

The most straightforward approach is to calculate the area for every possible pair of lines (i, j). We calculate width * height, where width is the distance between indices and height is the minimum of the two line heights. This approach involves a nested loop, leading to O(N²) time complexity, which is far too slow for large inputs where n can reach 100,000.

python
# Brute force: nested loops
def brute_force(height):
    max_area = 0
    for i in range(len(height)):
        for j in range(i + 1, len(height)):
            area = (j - i) * min(height[i], height[j])
            max_area = max(max_area, area)
    return max_area
The Two-Pointer Insight

The true insight here is to start with the widest possible container and greedily work inward. Since the water level is limited by the shorter wall, moving the taller wall inward will always decrease the width without any chance of increasing the height bottleneck. Therefore, the only way to potentially find a larger area is to move the shorter wall inward, looking for a taller replacement.

Optimal Strategy: Greedy Boundary Convergence

We place two pointers at the absolute edges of the array. At each step, we calculate the area formed by the current walls and always move the pointer pointing to the shorter wall, as it is the current limiting factor. We keep track of the maximum area encountered, converging in O(N) because each step moves one of the pointers, ensuring we scan every wall exactly once.

python
# Optimal: two pointers
def max_area(height):
    l, r, max_a = 0, len(height) - 1, 0
    while l < r:
        area = (r - l) * min(height[l], height[r])
        max_a = max(max_a, area)
        if height[l] < height[r]:
            l += 1
        else:
            r -= 1
    return max_a
Worked Example:[1, 8, 6, 2, 5, 4, 8, 3, 7]
0
1
L
1
8
2
6
3
2
4
5
5
4
6
8
7
3
8
7
R
We start Left at index 0 (1) and Right at index 8 (7). Width is 8, height is min(1,7) = 1. Area is 8.
0
1
1
8
L
2
6
3
2
4
5
5
4
6
8
7
3
8
7
R
Since 1 is shorter than 7, we move Left right. Left is at 8, Right at 7. Width is 7, height is 7. Area is 49 (new record!).
0
1
1
8
L
2
6
3
2
4
5
5
4
6
8
7
3
R
8
7
Since 7 is shorter than 8, we move Right left to index 7 (3). Width is 6, height is 3. Area is 18.
Interactive Strategy Visualization

Fluid Intuition

Geometric Optimization Trace

L
R
1
0
8
1
6
2
2
3
5
4
4
5
8
6
3
7
7
8
WIDTH
8
MIN HEIGHT
1
CURRENT AREA
8
MAX AREA
8

Key Insight

Area is strictly limited by the shorter wall. Moving the taller wall only decreases width without any possibility of a taller bottleneck.

Strategy

Always move the pointer pointing to the shorter line. It is the only way to potentially find a taller line to offset the width reduction.

O(N²) Brute Force -> O(N) Greedy Boundary Scan