Solving Container With Most Water – LeetCode Problem

Learn how to find the best pair of lines to hold the most water. We’ll solve it using brute force and an optimized two-pointer approach.

We are given an integer array height that contains the heights of n vertical lines drawn on the x-axis. The endpoints of the i-th line are (i, 0) and (i, height[i]).

Our goal is to find two lines that, along with the x-axis, form a container that holds the most water. This means we need to return the maximum area formed between any two lines and the x-axis.

The area of such a container is calculated by:

• Width: the distance between the two lines (i.e., the difference in their indices).
• Height: the height of the shorter of the two lines (since water can't go above the shorter one).

We’ll solve this problem using two different approaches: the Brute Force Approach and the Two Pointer Approach.

Brute Force Approach

In this approach, we check all possible pairs of lines, calculate the area formed between each pair, and track the maximum area found.

Here's the Java method for this approach:

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

The time and space complexity of this approach are O(n²) and O(1).

Two Pointer Approach

In this optimized approach, we use two pointers: one at the beginning (left) and one at the end (right) of the array.

We calculate the area between the two lines pointed to by left and right. Then, we move the pointer pointing to the shorter line inward—either left++ or right-- — because moving the taller line won’t help increase the area.

Here’s the Java implementation:

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

    while (left < right) {
        int h = Math.min(height[left], height[right]);
        int w = right - left;
        int area = h * w;
        maxArea = Math.max(maxArea, area);

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxArea;
}

Why do we move the shorter line?

Because the height of the container is determined by the shorter line. Keeping it won’t increase the area. But moving it inward might find a taller line that results in a larger area, even if the width becomes smaller.

The time and space complexity of this approach are O(n) and O(1).

These are the two common approaches to solve the "Container With Most Water" problem. Thanks for reading, and Happy Coding!