Container With Most Water

How it works

Using two pointers lets us efficiently search for the maximum area without checking every pair.
We start with the widest container (left at start, right at end).
The height is limited by the shorter line, so to potentially increase the area, we must move the pointer at the shorter line inward.
Moving the taller line never helps because it keeps the height the same but reduces the width.
By always moving the shorter side, we explore all meaningful possibilities.

Steps

1. Initialize two pointers:
   • l = 0
   • r = len(heights) - 1
2. Set res = 0 to store the maximum area.
3. While l < r:
   • Compute the current area: area = min(heights[l], heights[r]) * (r - l)
   • Update res with the maximum area so far.
   • Move the pointer at the shorter height:
     • If heights[l] <= heights[r], move l right.
     • Otherwise, move r left.
4. Return res after the pointers meet.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Moving the Wrong Pointer

The algorithm requires moving the pointer at the shorter height inward. Moving the taller pointer instead never increases the area (since height is limited by the shorter side) and can cause the algorithm to miss the optimal solution.

Confusing This Problem with Trapping Rain Water

Unlike the Trapping Rain Water problem where you need to sum water trapped between bars, this problem finds a single container formed by two lines. Applying the wrong mental model leads to incorrect area calculations.

Off-by-One Errors in Width Calculation

The width between indices l and r is r - l, not r - l + 1. Using the wrong formula overestimates the area by one unit for every pair, leading to incorrect results.

from typing import List

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

        while l < r:
            area = min(heights[l], heights[r]) * (r - l)
            res = max(res, area)
            if heights[l] <= heights[r]:
                l += 1
            else:
                r -= 1
        return res

class Solution {
public:
    int maxArea(vector<int>& heights) {
        int l = 0;
        int r = heights.size() - 1;
        int res = 0;

        while (l < r) {
            int area = min(heights[l], heights[r]) * (r - l);
            res = max(res, area);

            if (heights[l] <= heights[r]) {
                l++;
            } else {
                r--;
            }
        }
        return res;
    }
};