Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th 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.

Additional information

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

Example 1:

Input: height = [1,7,2,5,4,7,3,6]

Output: 36

Example 2:

Input: height = [1, 1]

Output: 1

Brute Force (Time Limit Exceeded)

Intuition
The simplest approach is to consider every possible pair of lines and calculate the area of water they can contain. The area formed by two lines at indices i and j is determined by the shorter line and the distance between them. Specifically, Area = min(height[i], height[j]) * (j - i). We can iterate through all pairs and keep track of the maximum area found.

Algorithm

1. Initialize max_area to 0.
2. Iterate l (left index) from 0 to n-1.
3. Iterate r (right index) from l + 1 to n-1.
4. Calculate the current area: area = (r - l) * min(height[l], height[r]).
5. Update max_area if the current area is larger.
6. Return max_area.

def max_area(height: list[int]) -> int:
    res = 0
    
    for l in range(len(height)):
        for r in range(l + 1, len(height)):
            area = (r - l) * min(height[l], height[r])
            res = max(res, area)
            
    return res

Time & Space Complexity

• Time complexity: O(n^2)

• Reason: We check every pair of lines using nested loops.

• Space complexity: O(1)

• Reason: We only use a single variable to store the result.

Two Pointers (Optimal)

Intuition
To optimize, we can start with the widest possible container (indices 0 and n-1) and try to see if we can get a better area by moving inward. The area is limited by the shorter line. If we move the pointer pointing to the longer line, the width decreases, and the height remains limited by the shorter line (or becomes even smaller), so the area can never increase. Therefore, to potentially find a larger area, we must always move the pointer pointing to the shorter line.

Algorithm

1. Initialize l to 0 and r to len(height) - 1.
2. Initialize res to 0.
3. While l < r:

• Calculate the current area: area = (r - l) * min(height[l], height[r]).
• Update res with the maximum area found.
• If height[l] < height[r], increment l (move left pointer right).
• Otherwise, decrement r (move right pointer left).

4. Return res.

def max_area(height: list[int]) -> int:
    l, r = 0, len(height) - 1
    res = 0

    while l < r:
        res = max(res, min(height[l], height[r]) * (r - l))
        if height[l] < height[r]:
            l += 1
        else:
            r -= 1
            
    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: The pointers l and r move towards each other, processing each element at most once.

• Space complexity: O(1)

• Reason: We use constant extra space for pointers and the result variable.