Container With Most Water

Share

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container that holds the most water. Return the maximum amount of water a container can store.

Example 1
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: Lines at indices 1 and 8 (values 8 and 7). Width = 7, height = min(8,7) = 7. Area = 49.
Example 2
Input: height = [1,1]
Output: 1
Constraints:

Contents

Approach 1: Brute Force O(n²)

Try every pair of lines and compute the contained area.

Java
public int maxArea(int[] height) {
    int max = 0;
    for (int i = 0; i < height.length - 1; i++) {
        for (int j = i + 1; j < height.length; j++) {
            int area = (j - i) * Math.min(height[i], height[j]);
            max = Math.max(max, area);
        }
    }
    return max;
}

Approach 2: Two Pointers O(n)

Key insight: Area = width × min(height[left], height[right]). Width decreases as we move pointers inward. To maximise area we must try to increase height, so we always move the pointer pointing at the shorter line.

Why? Moving the taller line inward can only decrease or maintain width while the height is still limited by the shorter line. So moving the shorter line gives a chance to find a taller one.

Java
public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxWater = 0;

    while (left < right) {
        int width  = right - left;
        int minH   = Math.min(height[left], height[right]);
        maxWater   = Math.max(maxWater, width * minH);

        // Move the shorter line inward
        if (height[left] <= height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}

Complexity Analysis
ApproachTimeSpace
Brute ForceO(n²)O(1)
Two PointersO(n)O(1)