11. Container With Most Water Medium

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, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:
Input: height = [1,1]
Output: 1

Approach

Input: An integer array height.

Output: Find the two lines that hold the most water with the x-axis.

This is a classic opposite-direction two pointers problem.

Core Logic

Every time we choose two lines to form a container, the capacity is determined by the shorter of the two lines:

• Height: min(height[left], height[right])
• Width: right - left
• Area (Capacity): area = height * width

Movement Strategy

Compare the heights at the two ends each time:

• Move the pointer that points to the shorter line towards the center (trying to find a taller line).
• Because the shorter line restricts the water's height, replacing it is the only way we could potentially get a larger area.

Algorithm Flow

1. Initialize left and right pointers: left = 0, right = n - 1
2. Loop until the two pointers meet:
   • Calculate the current area and update the maximum value.
   • Move the pointer with the shorter height.
3. Return the maximum area.

Implementation

python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # Initialize left and right pointers
        left, right = 0, len(height) - 1
        max_area = 0  # To record the maximum capacity

        # Two pointers move towards each other
        while left < right:
            # Calculate the area with current left and right pointers
            width = right - left
            h = min(height[left], height[right])
            area = width * h
            max_area = max(max_area, area)

            # Move the pointer with the smaller height (moving the taller one only decreases area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

javascript

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let left = 0;
    let right = height.length - 1;
    let maxArea = 0;

    while (left < right) {
        const h = Math.min(height[left], height[right]);
        const w = right - left;

        const area = w * h;
        maxArea = Math.max(maxArea, area);

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

11. Container With Most Water (English)11. 盛最多水的容器 (Chinese)