Dmitry Bardt | Container With Most Water. Two Pointer Solution That Actually Makes Sense

Move the shorter line's pointer inward—keeping it guarantees you'll never find a larger area.

I spent an embarrassing amount of time trying to brute force this problem during my first technical interview. Two nested loops, checking every possible pair of lines, watching the interviewer's smile slowly fade as my solution hit O(n²). Then they dropped the hint: "What if you started from both ends?" That's when everything clicked.

Understanding the Problem Visually

Picture yourself looking at a bar chart. Each bar represents a vertical line, and you need to find which two lines can hold the most water between them. The water level is limited by the shorter of the two lines—just like how water overflows from the lowest point of a container.

Here's what tripped me up initially: the area isn't just about finding the tallest lines. It's the product of the distance between lines and the height of the shorter line. A wide container with medium-height walls might hold more than a narrow container with tall walls.

def maxArea(self, height: List[int]) -> int:
    """
    Find maximum water container area using two pointers.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(height) - 1
    max_water = 0
    
    while left < right:
        # Calculate current area
        width = right - left
        current_height = min(height[left], height[right])
        current_area = width * current_height
        max_water = max(max_water, current_area)
        
        # Move pointer of shorter line
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_water

Why Moving the Shorter Pointer Works

This was the "aha" moment that changed everything for me. When you have two pointers at positions left and right, the area is:

Width: right - left
Height: min(height[left], height[right])

Now here's the crucial insight: if you move the pointer pointing to the taller line, you're guaranteed to get a smaller area. Why? The width decreases by 1, and the height can't increase (it's still limited by the shorter line).

But when you move the pointer at the shorter line, you at least have a chance of finding a taller line that could give you a larger area despite the reduced width.

# Let me show you with actual numbers
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

# Initial state: left=0 (height=1), right=8 (height=7)
# Area = 8 * min(1, 7) = 8 * 1 = 8

# If we moved right pointer: left=0, right=7
# Area = 7 * min(1, 3) = 7 * 1 = 7  (worse!)

# Instead, move left pointer: left=1, right=8
# Area = 7 * min(8, 7) = 7 * 7 = 49  (much better!)

Step-by-Step Walkthrough

Let me trace through a complete example so you can see the decision-making process:

def maxAreaWithLogging(height):
    """Same algorithm but with detailed logging"""
    left, right = 0, len(height) - 1
    max_water = 0
    step = 0
    
    print(f"Starting with array: {height}")
    
    while left < right:
        width = right - left
        current_height = min(height[left], height[right])
        current_area = width * current_height
        
        print(f"Step {step}: left={left}({height[left]}), "
              f"right={right}({height[right]}), area={current_area}")
        
        max_water = max(max_water, current_area)
        
        # Decision point
        if height[left] < height[right]:
            print(f"  → Moving left pointer (shorter line)")
            left += 1
        else:
            print(f"  → Moving right pointer (shorter line)")
            right -= 1
        
        step += 1
    
    print(f"Maximum area found: {max_water}")
    return max_water

# Example run
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
maxAreaWithLogging(height)

Optimization Tricks I've Learned

After solving this problem dozens of times (yes, I practice before interviews), I've picked up some optimizations that can shave off precious milliseconds:

def maxAreaOptimized(self, height: List[int]) -> int:
    """Optimized with early termination and fewer calculations"""
    left, right = 0, len(height) - 1
    max_water = 0
    
    while left < right:
        # Calculate area with single min() call
        if height[left] < height[right]:
            h = height[left]
            max_water = max(max_water, h * (right - left))
            # Skip smaller heights on left
            while left < right and height[left] <= h:
                left += 1
        else:
            h = height[right]
            max_water = max(max_water, h * (right - left))
            # Skip smaller heights on right
            while left < right and height[right] <= h:
                right -= 1
    
    return max_water

The key optimization here is skipping over lines that are shorter than or equal to the current one. If we're moving away from a line of height 5, there's no point checking lines of height 3 or 4—they can't possibly give us a better area.

Why Other Approaches Fall Short

I've seen people try different strategies, and here's why they don't work:

Sorting first? Nope. The position of lines matters for calculating width. Once you sort, you lose that crucial information.

Dynamic programming? Overkill. There's no overlapping subproblems here. Each decision is independent.

Divide and conquer? You might think about splitting the array and conquering each half, but the maximum area might span across your split point.

The two-pointer approach works because it systematically eliminates possibilities that can't be optimal, checking only O(n) combinations instead of O(n²).

Common Pitfalls to Avoid

Moving both pointers simultaneously - You need to make a deliberate choice based on heights
Forgetting to handle equal heights - When heights are equal, move either pointer (I prefer moving right for consistency)
Off-by-one errors - Remember the width is right - left, not right - left + 1
Integer overflow - In languages like C++, use long long for large inputs
Overthinking the problem - Trust the greedy approach; you don't need to track previous states

Key Takeaways

The two-pointer technique transforms this from O(n²) brute force to elegant O(n)
Always move the pointer pointing to the shorter line—this is the greedy choice that works
Width decreases as pointers converge, so we need increasing heights to compensate
The optimization of skipping smaller heights can provide significant speedup on certain inputs
This pattern appears in many problems: trapping rainwater, 3Sum, and palindrome checking

Container With Most Water. Two Pointer Solution That Actually Makes Sense

Learn why the two pointer approach works for the Container With Most Water problem with visual intuition, code walkthrough, and common mistakes to avoid