Container With Most Water in Python: Optimal Two Pointer Solution Explained

Problem Overview

In the Container With Most Water problem, you are given an array where each element represents the height of a vertical line drawn at that index. The goal is to find two lines that, together with the x-axis, form a container capable of holding the maximum amount of water.

Problem Visualization

Each value in the array represents a vertical line. The water trapped between any two lines depends on the distance between them (width) and the shorter of the two lines (height).

#source - Leetcode

In the diagram above, the highlighted lines form the container that holds the maximum water. Even though some lines are taller, the distance between them is smaller, resulting in less area.

Key Insight

The amount of water a container can store is calculated using:

area = min(height[left], height[right]) × (right - left)
  

As the pointers move inward, the width always decreases. Therefore, the only way to potentially increase the area is by increasing the limiting height — the smaller of the two heights.

Optimal Strategy: Two Pointer Technique

To avoid checking every possible pair, we use two pointers:

• One pointer at the beginning of the array
• One pointer at the end of the array

At each step, the area is calculated, and the pointer pointing to the shorter line is moved inward. This greedy decision is safe because the shorter line is the bottleneck for the current container.

Algorithm Steps

1. Initialize two pointers at the start and end of the array.
2. Calculate the area formed by the lines at both pointers.
3. Update the maximum area if the current area is larger.
4. Move the pointer with the smaller height inward.
5. Repeat until the pointers meet.

Python Implementation

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = 0
        r = len(height) - 1
        max_area = 0

        while l < r:
            current_area = min(height[l], height[r]) * (r - l)
            max_area = max(max_area, current_area)

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1

        return max_area
  

Why This Approach Works

This method works because moving the taller line cannot improve the area — the height of the container is limited by the shorter line. By always moving the limiting pointer, we ensure that every move has the potential to increase the container height while accepting a reduced width.

Complexity Analysis

• Time Complexity: O(n), where n is the number of lines.
• Space Complexity: O(1), as no extra space is used.

Pattern Summary

This problem is a classic example of a greedy two-pointer approach. It combines pair-based decision-making with a monotonic property (shrinking width) and a clear limiting factor (minimum height), allowing an optimal linear-time solution.

Understanding this pattern helps solve many optimization problems where checking all combinations is unnecessary and inefficient.