11. Container With Most Water

Problem Description

Given an array height representing the heights of vertical lines, find two lines that, together with the x-axis, form a container that holds the most water. The area of the container is determined by the shorter line's height and the distance between the lines. You cannot slant the container.

Solution: Two Pointers

The optimal solution uses a two-pointer approach. The idea is to maintain two pointers, left and right, initially at the beginning and end of the height array, respectively.

1. Calculate Area: In each iteration, calculate the area formed by the lines at left and right: area = min(height[left], height[right]) * (right - left).

2. Update Maximum Area: Update the maximum area (maxArea) if the current area is greater.

3. Move Pointers: Move the pointer pointing to the shorter line inwards. This is because moving the pointer pointing to the taller line will never increase the area, as the height will be limited by the shorter line. The only way to potentially increase the area is to find a taller line farther away.

4. Repeat: Repeat steps 1-3 until the pointers cross each other (left < right).

Why this works:

The algorithm cleverly avoids exploring all possible pairs of lines. It implicitly prunes the search space. By always moving the pointer to the shorter line, it ensures that the next iteration has the potential to improve the maximum area.

Code (Python)

def maxArea(height):
    left = 0
    right = len(height) - 1
    maxArea = 0
 
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        maxArea = max(maxArea, area)
 
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
 
    return maxArea

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the height array. The pointers traverse the array at most once.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code in other Languages

The logic remains the same across different programming languages. Here are examples in a few other languages:

Java:

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

C++:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int maxArea = 0;
 
        while (left < right) {
            int area = min(height[left], height[right]) * (right - left);
            maxArea = max(maxArea, area);
 
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
 
        return maxArea;
    }
};

JavaScript:

var maxArea = function(height) {
    let left = 0;
    let right = height.length - 1;
    let maxArea = 0;
 
    while (left < right) {
        let area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);
 
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
 
    return maxArea;
};

These examples demonstrate the adaptability of the two-pointer approach across various programming languages. The core algorithm remains consistent, showcasing its efficiency and elegance.