Container With Most Water

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.

idea

• use two pointers to find the maximum area. The area is calculated as the minimum of the two heights multiplied by the distance between the two pointers.
• move the pointer that points to the shorter height towards the other pointer. This is because the area is limited by the shorter height, so we want to find a taller height to maximize the area.
• continue this process until the two pointers meet.
• return the maximum area found.
• the time complexity is O(n) and the space complexity is O(1).

Generalized Concept	Specific in This Algorithm
Invariant	At every step, we consider the maximum area formed between two lines at left and right.
Greedy Decision by Structure	Move the pointer pointing to the shorter height, because only that can potentially lead to a larger minimal height.
No Missed Opportunities	By moving only the smaller height pointer, every possible improvement (taller line) is explored. No possibility is skipped.
Problem Decomposition	Break down the large problem ("find max area between any two lines") into small steps ("what's the max area between current left and right?").
Monotonic Progress	Each pointer moves inward (either left++ or right--), strictly reducing the width and guaranteeing no cycles.
Optimal Substructure	The maximum area at the current step depends only on the two heights and the distance — no hidden dependency. Thus, solving each step optimally builds the overall solution.

corner cases

• if the array is empty, return 0.
• if the array has only one element, return 0.

code

def maxArea(self, height: List[int]) -> int:
    left, right = 0, len(height) - 1
    max_area = 0
    while left < right:
        width = right - left
        max_area = max(max_area, min(height[left], height[right]) * width)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area