Problem Statement #

Given an array of n non-negative integers [a₁, a₂, ..., aₙ], where each element represents a point at coordinate (i, aᵢ). Imagine n vertical lines are drawn such that the two endpoints of line i are at (i, aᵢ) and (i, 0).

Your task: Find two lines that, together with the x-axis, form a container that holds the maximum amount of water.

Constraints:

• You cannot slant the container (it must be vertical)
• The array length n is at least 2
• Water will overflow at the shorter of the two lines

Visual Example #

Consider the array [1, 8, 6, 2, 5, 4, 8, 3, 7]:

     |                   |
     |                   |       |
     |   |               |       |
     |   |       |       |       |
     |   |       |   |   |       |
     |   |       |   |   |   |   |
     |   |   |   |   |   |   |   |
 |   |   |   |   |   |   |   |   |
─┴───┴───┴───┴───┴───┴───┴───┴───┴─
 0   1   2   3   4   5   6   7   8

The maximum area is formed between index 1 (height=8) and index 8 (height=7), giving us an area of 7 × 7 = 49.

Mathematical Foundation #

Before diving into solutions, let’s establish the mathematical basis:

Area of Container = Base × Height

Where:

• Base = Distance between two pillars = j - i
• Height = Minimum of the two pillar heights = min(height[i], height[j])

The height must be the minimum because water will overflow at the shorter pillar. Think of it like pouring water between two walls of different heights—the water level can only rise to the height of the shorter wall.

Solution 1: Brute Force Approach #

Algorithm Explanation #

The most straightforward approach is to examine every possible pair of pillars and calculate the area they form. This guarantees we’ll find the maximum area, but at the cost of computational efficiency.

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

Implementation Logic #

1. Use two nested loops to iterate through all possible pairs
2. For each pair (i, j), calculate the area: (j - i) × min(height[i], height[j])
3. Track and update the maximum area found
4. Return the maximum area after checking all combinations

Key Design Decision: The inner loop starts at i + 1 rather than 0 for two important reasons:

• Avoid zero-width containers: Using the same pillar twice would result in base = 0
• Eliminate duplicate pairs: The pair (i, j) is identical to (j, i), so we only need to check each combination once

Code Implementation #

var maxArea = function(height) {
    let max = 0;
    
    // Outer loop: first pillar
    for (let i = 0; i < height.length; i++) {
        // Inner loop: second pillar (starting from i+1 to avoid duplicates)
        for (let j = i + 1; j < height.length; j++) {
            // Calculate area: base × height
            const area = (j - i) * Math.min(height[i], height[j]);
            
            // Update maximum if current area is larger
            if (area > max) {
                max = area;
            }
        }
    }
    
    return max;
};

Performance Analysis #

Pros:

• Simple and intuitive to understand
• Guaranteed to find the correct answer
• No complex logic or edge cases

Cons:

• Inefficient for large inputs
• Checks many unnecessary combinations
• O(n²) time complexity makes it impractical for arrays with thousands of elements

For an array of size 1000, this approach would perform approximately 500,000 comparisons. We can do much better.

Solution 2: Optimized Two-Pointer Approach #

The Key Insight #

The breakthrough comes from asking: Do we really need to check every combination?

Consider the area formula again: Area = Width × Height

To maximize area, we want to maximize both width and height. Here’s the crucial observation:

1. Maximum possible width occurs when pointers are at opposite ends of the array
2. Height is limited by the shorter of the two pillars
3. Moving inward from the taller pillar can never increase the area—we lose width while the height remains constrained by the shorter pillar

This leads us to a greedy algorithm: always move the pointer at the shorter pillar inward, hoping to find a taller pillar that compensates for the lost width.

Algorithm Strategy #

1. Initialize: Place two pointers at the extreme ends (left = 0, right = n-1)
2. Calculate: Find the area with current pointers
3. Decide: Move the pointer at the shorter pillar inward
   • If height[left] < height[right], increment left
   • Otherwise, decrement right
4. Repeat: Continue until pointers meet
5. Return: The maximum area encountered

Why This Works #

Proof sketch:

• We start with maximum width
• We only eliminate configurations that cannot possibly yield a larger area
• When we move the shorter pillar inward, we’re searching for a taller pillar
• Moving the taller pillar inward would be pointless—we’d lose width without gaining height potential

Time Complexity: O(n) — we traverse the array once
Space Complexity: O(1) — only a few variables needed

Code Implementation #

var maxArea = function(height) {
    let maxArea = 0;
    let left = 0;
    let right = height.length - 1;
    
    // Calculate initial area with maximum width
    maxArea = (right - left) * Math.min(height[left], height[right]);
    
    // Move pointers toward each other
    while (right > left) {
        // Move pointer at shorter pillar
        if (height[left] > height[right]) {
            right--;
        } else {
            left++;
        }
        
        // Calculate area with new configuration
        const area = (right - left) * Math.min(height[left], height[right]);
        
        // Update maximum area if current is larger
        maxArea = Math.max(area, maxArea);
    }
    
    return maxArea;
};

Step-by-Step Example #

Let’s trace through [1, 8, 6, 2, 5, 4, 8, 3, 7]:

Step 1: left=0(h=1), right=8(h=7) → area = 8×1 = 8,  max=8
Step 2: left=1(h=8), right=8(h=7) → area = 7×7 = 49, max=49
Step 3: left=1(h=8), right=7(h=3) → area = 6×3 = 18, max=49
Step 4: left=1(h=8), right=6(h=8) → area = 5×8 = 40, max=49
Step 5: left=2(h=6), right=6(h=8) → area = 4×6 = 24, max=49
...continues until left meets right

The maximum area of 49 is found and returned.

Comparative Analysis #

Performance Comparison #

For an array of size 10,000:

• Brute Force: ~50,000,000 operations
• Two Pointer: ~10,000 operations

That’s a 5,000× speedup!

Key Takeaways #

1. Brute force is a valid starting point but rarely optimal for interview or production scenarios
2. Mathematical analysis of the problem constraints reveals optimization opportunities
3. Greedy algorithms work when we can prove that local optimal choices lead to global optimal solutions
4. Two-pointer technique is powerful for array problems involving pairs or ranges
5. Trade-offs matter: The two-pointer approach is harder to understand initially but vastly more efficient

Common Pitfalls to Avoid #

1. Moving both pointers simultaneously — this can skip the optimal solution
2. Moving the taller pillar — this can only decrease the area
3. Not handling edge cases — ensure the array has at least 2 elements
4. Integer overflow — for very large inputs, ensure proper data types

Practice Problems #

To master this technique, try these similar problems:

• Trapping Rain Water (harder version with multiple containers)
• 3Sum Problem (extending two-pointer to three pointers)
• Minimum Window Substring (two-pointer with different movement rules)