mediumTwo Pointers

Container With Most Water

Array values are heights of vertical lines at positions 0, 1, and so on. Choose two lines to maximize the area between them: their distance multiplied by the shorter height.

LeetCode ↗

Work through the cases

3 examples

Input notation

At least two nonnegative heights separated by spaces.

Expected result

The maximum area.

Case 1

Input

3 1 2 4

Expected output

Case 2

Input

1 1

Expected output

Case 3

Input

0 0

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is to try every pair (i,j) and take \min(height[i],height[j]) × (j-i). Correct, but O(n^2). n ≤ 10^5 will time out. The bottleneck is treating every pair independently and ignoring that height is fixed by the shorter line. Start from the widest interval [0,n-1]: moving the taller end inward shrinks the width while the height is still capped by the shorter line, so the area cannot improve. We must drop the shorter line and look for a taller one. So we shrink from both ends, always moving the shorter side. Each index is visited at most once.

We use two pointers l and r to point to the left and right ends of the array, respectively, i.e., l = 0 and r = n - 1, where n is the length of the array.

Next, we use a variable ans to record the maximum capacity of the container, initially set to 0.

Then, we start a loop. In each iteration, we calculate the current capacity of the container, i.e., min(height[l], height[r]) × (r - l), and compare it with ans, assigning the larger value to ans. Then, we compare the values of height[l] and height[r]. If height[l] < height[r], moving the r pointer will not improve the result because the height of the container is determined by the shorter vertical line, so we move the l pointer. Otherwise, we move the r pointer.

After the iteration, we return ans.

The time complexity is O(n), where n is the length of the array height. The space complexity is O(1).

class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int ans = 0;
        while (l < r) {
            int t = Math.min(height[l], height[r]) * (r - l);
            ans = Math.max(ans, t);
            if (height[l] < height[r]) {
                ++l;
            } else {
                --r;
            }
        }
        return ans;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.