LeetCode Container with Most Water: The Two‑Pointer Solution

In the realm of algorithms, water can manifest in many ways. It's an interesting concept because water is ‑ by its very nature ‑ fluid, and unencumbered by the sorts of rigidity and limitations we see in development (for a decent example, see just how 'random' Math.random() really is).

The 'Container with Most Water' problem offers a picturesque metaphor that helps encapsulate a foundational algorithmic strategy. Let's take a look.

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 it's 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

As with most problems in web development, there is usually more than one route to a valid solution. In this case, there's a classic two‑pointer approach, which is both intuitive and efficient. Here's a rough outline of 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:

   The key here is to always move the shorter of the two pointers, because by moving the taller one, the width decreases without any guarantee of the height increasing, which would then possibly reduce the area.

4. Iterate:

   Continue moving the pointers toward 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 left pointer (since both heights are equal we could actually move either but I've defaulted to left where both heights are equal).
4. Now, left points to height=5 and right still at height=2. There are now seven steps between the two points (8 ‑ 1).
5. The possible area is 2 * (8 ‑ 1) = 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.

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.

For web developers, mastering these types of algorithmic strategies can significantly speed up data processing tasks and optimise performance‑intensive routines.