ProblemMediumLeetCode #116 min read

Container With Most Water

Maximize trapped area between two vertical lines — two pointers from each end.

arraystwo-pointers

Intro

Given heights of vertical lines, pick two that together with the x-axis hold the most water. Brute force is O(n²); two-pointer brings it to O(n).

Key insight

The shorter line bounds the area. Moving the longer line inward can only reduce the width without raising the bound — move the shorter one.

Approach

1left = 0, right = n - 1.
2Compute area = min(h[left], h[right]) * (right - left).
3Move whichever pointer has the smaller height inward; track best.

Complexity

Time

O(n)

Space

O(1)

Code

Snippetjava

int maxArea(int[] h) {
    int l = 0, r = h.length - 1, best = 0;
    while (l < r) {
        best = Math.max(best, Math.min(h[l], h[r]) * (r - l));
        if (h[l] < h[r]) l++; else r--;
    }
    return best;
}

Pitfalls

Moving the taller pointer — wastes the shrunk width on the same shorter bound.
Computing area as max instead of min of the two heights.

Variants & follow-ups

Trapping Rain Water (LC 42)