LeetCode Container with Most Water: The Two‑Pointer Solution

Given a row of wall heights, which two walls would hold the most water between them? We could check every pair, but there is a useful shortcut: start at the ends and move the shorter wall inwards.

That's the idea behind the two‑pointer solution to Container with Most Water. Let's work through it with a diagram and some TypeScript.

Understanding the Problem

Imagine you're at the seashore with several vertical lines drawn in the sand. Each line represents a wall of a different height. If it rains, and you were to place these walls parallel to each other, forming containers, which two walls would trap the most amount of water?

Although LeetCode remains as guilty as ever of over‑technicalising the description (which I'll try and summarise in a minute), at its core this is a problem about finding the largest area between sets of barriers.

Problem Statement

Given an array representing wall heights, find two lines that together with the x‑axis form a container that can hold the most water.

Throughout this article, we're going to use the example [2, 5, 3, 6, 1, 7, 2, 3, 2] simply because I spent ages in Photoshop knocking together this diagram to offer a visual example. It helps that I've already worked out the answer too so can show you the water. So, channelling my very best classic Blue Peter impression, here's one that I made earlier:

Now that we (hopefully) understand the problem, how can we programmatically determine which two numbers from this array (and any other) can trap the maximum amount of water between them?

Two‑Pointer Approach

Checking every pair would work, but the two‑pointer approach lets us discard pairs that cannot improve on an area we have already checked. Here's how it works:

1. Initialise:

   Place two pointers at the beginning and end of the array. This represents the widest possible container.

2. Calculate Area:

   Calculate the area between the two pointers. This is min(height[left], height[right]) * (right - left).

3. Move the Pointers:

   Move the pointer at the shorter wall. Keeping that wall and moving the taller one inwards cannot improve the area: the width shrinks, and the shorter wall still limits the height. If the heights match, either pointer can move; this implementation moves right.

4. Iterate:

   Continue moving the pointers towards each other until they meet, updating the maximum area whenever a larger one is found.

The Code

Channelling my best Blue Peter presenter impression again, here's one I made earlier using TypeScript:

const maxArea = (height: number[]): number => {
  let left = 0;
  let right = height.length - 1;
  let max_area = 0;

  while (left < right) {
    const minHeight = Math.min(height[left], height[right]);
    max_area = Math.max(max_area, minHeight * (right - left));

    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }

  return max_area;
};

A Step‑by‑Step through the Solution

So, reverting back to our example and diagram above, here's what happens when we plug [2, 5, 3, 6, 1, 7, 2, 3, 2] into our function:

1. Start with pointers (left and right) at positions 0 (height=2) and 8 (height=2).
2. The area is 2 * (8 - 0) = 16.
3. Move the right pointer. The heights are equal, so either pointer could move; the else branch in this code moves right.
4. Now, left remains at index 0 (height=2) and right is at index 7 (height=3). There are seven steps between them: 7 - 0.
5. The possible area is 2 * (7 - 0) = 14.
6. We continue moving the pointers, recalculating the area at each step.
7. At the end of this process, the maximum area will be between positions 1 (height=5) and 5 (height=7). The trapped area is 5 * (5 - 1) = 20. These are zero‑based array indices; the diagram labels the same walls as positions 2 and 6.

Wrapping‑up

The 'Container with Most Water' problem does an elegant job of illustrating the efficiency of the two‑pointer technique. By strategically moving pointers and making calculated decisions, we reduce a potentially quadratic problem to a linear one.

The useful lesson here is knowing why a pair can be ruled out. Each step moves one pointer, so we visit at most n - 1 pairs instead of checking every combination.