Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is an array of heights. Each height represents a vertical line drawn at that index.

The task is to pick two lines that, together with the x-axis, form a container that holds the most water.

The area is determined by two things:

  • the width between the two chosen indices
  • the shorter of the two heights

So for indices left and right, the area is:

(right - left) * min(height[left], height[right])

That is the whole problem. The challenge is finding the best pair without checking every pair.

The key insight

The shorter wall is always the bottleneck.

If the left wall is shorter than the right wall, then the current container’s height is capped by the left wall. Moving the right pointer inward makes the container narrower, and it does not remove the bottleneck on the left. That means keeping the same short left wall cannot produce a better answer.

So when one side is shorter, that side is the only one worth moving.

This is what makes the two-pointer solution work:

  • start with the widest possible container
  • record its area
  • move the pointer at the shorter wall
  • repeat until the pointers meet

How to derive the optimal solution

A good way to derive it is to start from brute force and then remove wasted work.

Brute force would try every pair of indices. That works, but it costs O(n^2), which is too slow for large inputs.

Now imagine the pointers are at the far ends of the array:

  1. This gives the maximum possible width.
  2. The area is limited by the shorter wall.
  3. If that shorter wall stays in place, any new container will have smaller width.
  4. So the only hope of improving the area is to find a taller replacement for the shorter wall.

That means each step can safely discard one index:

  • if height[left] <= height[right], advance left
  • otherwise, decrease right

Each index is visited at most once, so the final runtime is linear.

Best approach

The two-pointer solution is the best default:

  • Time: O(n)
  • Extra space: O(1)
  • Why it is optimal: it keeps the widest remaining candidate at every step and only discards positions that cannot lead to a better answer

Python solution

from typing import List


class Solution:
    def maxArea(self, heights: List[int]) -> int:
        left_index = 0
        right_index = len(heights) - 1
        best_area = 0

        while left_index < right_index:
            current_area = self._container_area(
                left_index=left_index,
                right_index=right_index,
                left_height=heights[left_index],
                right_height=heights[right_index],
            )
            best_area = max(best_area, current_area)

            # Only the shorter wall can be the limiting factor.
            # Move that pointer to look for a taller replacement.
            if heights[left_index] <= heights[right_index]:
                left_index += 1
            else:
                right_index -= 1

        return best_area

    @staticmethod
    def _container_area(
        left_index: int,
        right_index: int,
        left_height: int,
        right_height: int,
    ) -> int:
        width = right_index - left_index
        limiting_height = min(left_height, right_height)
        return width * limiting_height

Why this works

At every step, the algorithm evaluates the best container that uses the current outer boundaries.

After that, it throws away the shorter wall because that wall can never produce a better answer with any narrower window. A narrower window reduces width, and keeping the same limiting height cannot improve the area.

That is why the algorithm never misses the optimal pair even though it only checks O(n) containers.

The interview version to remember is:

start wide, compute area, and always move the shorter wall because the shorter wall is the only thing holding the area back.