Container With Most Water

Difficulty: Medium
Topics: Array, Two Pointers, Greedy
Link: https://leetcode.com/problems/container-with-most-water/

Problem Description

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

Constraints:

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

Solution

1. Problem Deconstruction

Technical Restatement
Given array height of length n, find indices i, j (i < j) maximizing:

\text{Area} = (j - i) \times \min(\text{height}[i], \text{height}[j])

Return the maximum possible area.

Beginner Explanation
Imagine vertical lines on a graph where each line’s height is given. We need to pick two lines to form a container with the x-axis. The container’s capacity depends on the shorter line’s height and the distance between the lines. Find the pair that gives the largest possible container.

Mathematical Formulation
Let $S = \{(i,j) \mid 0 \leq i < j < n\}$ . Compute:

\max_{(i,j) \in S} \left[ (j - i) \times \min(h_i, h_j) \right]

Constraint Analysis

$2 \leq n \leq 10^5$ :
- Brute-force pairwise checks ( $O(n^2)$ ) are computationally infeasible.
- Requires $O(n)$ or $O(n \log n)$ algorithm.
$0 \leq \text{height}[i] \leq 10^4$ :
- Zero-height lines can still form containers (e.g., [0,5] has area 0).
- Edge case: All elements except two are zero (e.g., [0,5,0] → max area is 0).

2. Intuition Scaffolding

Analogies

Real-World Metaphor: Two people holding a water tank. Their combined reach (distance) and the shorter person’s height determine capacity.
Gaming Analogy: In a tower defense game, placing two towers to maximize coverage area (width × min height).
Math Analogy: Maximizing the product of two variables under monotonic constraints.

Common Pitfalls

Global Maxima Trap: Picking the two tallest lines ignores width (e.g., [9,1,1,1,9] → area 9×4=36 vs [1,8,6,...7] in Example 1).
Single-Pointer Greedy: Moving one pointer greedily (e.g., always forward) fails to explore all width/height tradeoffs.
Overlooking Zero-Height: Assuming non-zero heights may miss edge cases (e.g., [0,100] → area 0).
Symmetric Updates: Moving both pointers inward simultaneously risks skipping optimal pairs.
Early Termination: Stopping when area decreases once may miss later larger areas.

3. Approach Encyclopedia

Brute Force (Rejected)

Check all $O(n^2)$ pairs.

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

Complexity: Time $O(n^2)$ , Space $O(1)$ .

Optimal Two-Pointer Approach
Pseudocode:

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

Intuition:

Start with maximum width (left=0, right=n-1).
At each step, move the shorter line inward to seek a taller line, preserving potential for larger areas.

Complexity Proof:

Each iteration moves left or right by 1 → total $O(n)$ steps.
Space: $O(1)$ .

Visualization:

Initial: [1,8,6,2,5,4,8,3,7]  
         ^                 ^  
Step 1: Area = 1*8 = 8 → Move left.  
Step 2: New left=1 (height=8). Area = 7*7=49 → Keep.  
... Continue until pointers meet.

4. Code Deep Dive

Line-by-Line Annotations:

def maxArea(height):  
    left = 0                   # Start at widest possible left  
    right = len(height) - 1    # and right positions.  
    max_area = 0               # Track global maximum.  
    while left < right:  
        current_height = min(height[left], height[right])  
        current_width = right - left  
        current_area = current_height * current_width  
        max_area = max(max_area, current_area)  # Update global max.  
        if height[left] < height[right]:  
            left += 1          # Shorter line is left; try next.  
        else:  
            right -= 1         # Shorter line is right; try previous.  
    return max_area

Edge Case Handling:

Example 1: Correctly captures the 49 area by moving left past shorter lines.
Example 2: [1,1] → area 1×1=1.
All Zeros: Returns 0 as expected.

5. Complexity War Room

Hardware Analysis:

For $n=1e5$ , the loop runs 1e5 times. At ~3 operations per iteration, executes in ~0.3ms (modern CPU).

Approach Comparison:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n²)	O(1)	10/10	❌ (Fails for n=1e5)
Two-Pointer	O(n)	O(1)	9/10	✅ Optimal

6. Pro Mode Extras

Variants:

3D Version: Container with most water in 3D grid (complexity jumps to NP-Hard).
Multiple Pairs: Allowing k non-overlapping containers (dynamic programming).

Interview Cheat Sheet:

First Mention: “This is a two-pointer problem because we can greedily move pointers based on height comparisons.”
Key Insight: “Moving the shorter line preserves the chance to find a taller line, which may yield a larger area despite reduced width.”
Time/Space: Always state “O(n) time and O(1) space” upfront.

#11 - Container With Most Water