Container With Most Water

Difficulty: Medium | Acceptance: 58.20% | Paid: No

Topics: Array, Two Pointers, Greedy

• Examples
• Constraints
• Brute Force
• Two Pointer Technique
• Optimized Two Pointer with Early Termination

Examples

Input

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

Output

49

Explanation

The maximum area of water (blue section) the container can contain is 49.

Input

height = [1,1]

Output

1

Constraints

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

Brute Force

Intuition

Check every possible pair of lines to find the maximum area formed between them.

Steps

• Iterate through all pairs of lines (i, j) where i < j.
• For every pair, calculate the area as min(height[i], height[j]) * (j - i).
• Keep track of the maximum area seen so far.
• Return the maximum area.

def maxArea(height):
    max_area = 0
    for i in range(len(height)):
        for j in range(i + 1, len(height)):
            area = min(height[i], height[j]) * (j - i)
            max_area = max(max_area, area)
    return max_area

Complexity

• Time: O(n^2)
• Space: O(1)
• Notes: The algorithm checks all pairs of lines, resulting in quadratic time complexity.

Two Pointer Technique

Intuition

Use two pointers from both ends of the array and move the one pointing to the shorter line inward.

Steps

• Initialize two pointers at the start (left) and end (right) of the array.
• Calculate the area formed between the lines at left and right pointers.
• Move the pointer pointing to the shorter line inward to potentially find a taller line.
• Keep track of the maximum area encountered during this process.
• Stop when the pointers meet.

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

Complexity

• Time: O(n)
• Space: O(1)
• Notes: The algorithm makes a single pass through the array using two pointers, achieving linear time complexity.

Optimized Two Pointer with Early Termination

Intuition

Improve the standard two-pointer approach by early termination when further improvement is not possible.

Steps

• Initialize two pointers at the start and end of the array.
• Calculate area and move the shorter pointer inward while keeping track of maximum.
• Introduce early termination conditions based on remaining potential maximum area.
• Stop early if the maximum possible area with remaining width is less than current max.
• Return the maximum area found.

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0
    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)
        # Early termination optimization
        if max_area >= max(height) * (right - left):
            break
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Although it maintains O(n) complexity like the standard two-pointer, it can finish significantly earlier on some inputs.