11. Container With Most Water

Intuition

To maximize the amount of water a container can hold, we need to consider the widest possible distance between two lines and the shortest height among them, as the water is limited by the shorter line.

If we start with the widest container (the first and last lines), we can try moving the pointer pointing to the shorter line inward. This is because the only way to potentially find a taller line (which could increase the area) is to discard the shorter one. Repeating this process will help us find the container with the maximum area.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N)$

Code

public int maxArea(int[] heights) {
    int maxWater = 0; // To store the maximum area found
    int left = 0; // Left pointer starting at the beginning
    int right = heights.length - 1; // Right pointer starting at the end

    while (left < right) {
        // Height of the container is limited by the shorter line
        int currentHeight = Math.min(heights[left], heights[right]);
        
        // Width of the container is the distance between the two pointers
        int width = right - left;
        
        // Calculate the current area and update max if it's larger
        int currentArea = currentHeight * width;
        maxWater = Math.max(maxWater, currentArea);
        
        // Move the pointer pointing to the shorter line inward
        if (heights[left] < heights[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxWater; // Return the maximum area found
}