M.A.T.R.I.X

Appearance

Volume ITechnology

4.5.4 — Container With Most Water ​

LeetCode 11 · Medium · ★ Blind 75

The problem ​

Each number is the height of a vertical line. Pick two lines so that the container they form holds the most water.

height = [1,8,6,2,5,4,8,3,7]   →  49

The area between lines at l and r is:

\text{area} = \min(h[l],\, h[r]) \times (r - l)

The width is how far apart they are. The height is the shorter of the two walls, because water spills over the lower one.

Up to 100,000 lines, so O(n^2) is out.

Constraints:

  • Heights are non-negative.
  • The width between lines is simply the difference in their indices.

Plain English: You are given an array of vertical lines. You want to pick exactly two lines to act as the left and right walls of a water tank. The distance between the lines is the tank's width, and the shorter line is the tank's height. Find the tank that holds the most water.

The naive approach ​

The brute-force way is to check every possible pair of lines. You lock in a left line, then try every possible right line.

  • Why it fails: For 100,000 lines, checking every pair is O(n^2) time, which means up to 10 billion combinations. That's a guaranteed Time Limit Exceeded (TLE). It calculates the area for containers that could never logically be the biggest.

The pattern ​

Start with the widest possible container: one pointer at each end. That gives the maximum width, so any improvement has to come from height.

Now the decision. Which pointer moves?

Move the shorter wall inwards. Here is why that is safe.

The width shrinks on every move, no matter which pointer you move. That loss is unavoidable. So the only question is whether the height can grow enough to make up for it.

If you move the taller wall inwards, the height is still capped by the shorter wall, which has not changed. So the height cannot increase, and the width has decreased. Every container you could reach that way is smaller. Nothing is lost by never trying them.

If you move the shorter wall, you at least have a chance of finding a taller one.

So the shorter wall is a bottleneck that can never be part of a bigger container than the one you just measured. Discard it. That is the same discard proof as 4.5.2, applied to geometry instead of sums.

The ELI5 Analogy: Imagine you're building a rectangular fence for a dog, and you want maximum area. You start by putting the fence posts as far apart as possible. The only problem is, one fence post is 2 feet tall, and the other is 10 feet tall. The dog can just jump over the 2-foot post! The short post is ruining your fence. Moving the 10-foot post inwards won't help you; the 2-foot post is still the weak link. The only way to possibly get a better fence is to abandon the 2-foot post and try another one, hoping it's taller.

The solution ​

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

        while l < r:
            best = max(best, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1

        return best
ts
function maxArea(height: number[]): number {
  let l = 0, r = height.length - 1, best = 0;

  while (l < r) {
    best = Math.max(best, Math.min(height[l], height[r]) * (r - l));
    if (height[l] < height[r]) l++;
    else r--;
  }

  return best;
}

Measure first, then move. Measuring after moving would skip the widest container entirely.

When the two walls are equal, either move works, and the else branch handles it by moving r. It cannot cost you the answer: with equal heights, moving either one leaves the height capped at that same value, so both remaining containers are narrower and no taller. You could move both at once and save one iteration.

The l < r condition is what prevents an infinite loop. Every iteration moves exactly one pointer inwards, so the gap always shrinks and the loop always ends.

Code Walkthrough ​

  • l, r = 0, len(height) - 1: Start with the widest possible container.
  • best = max(...): Before we do any moving, we calculate the water this current container holds and update our max record.
  • if height[l] < height[r]: l += 1: If the left wall is the shorter one, we can never form a larger container using this left wall (since moving r inwards would only decrease the width without increasing the height constraint). So we abandon it and move l right.
  • else: r -= 1: If the right wall is shorter (or they are equal), we abandon the right wall and move r left.

Trace ​

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

lrheightsareamove
081, 71 × 8 = 8left is shorter → l++
188, 77 × 7 = 49right is shorter → r--
178, 33 × 6 = 18r--
168, 88 × 5 = 40equal → r--
158, 44 × 4 = 16r--

and so on downwards. The answer 49 was found on the second step and never beaten.

Complexity ​

O(n) time — the pointers move towards each other and cover the array once. O(1) space.

Let's derive it:

  • Time Complexity: O(n). We have two pointers, l and r, starting at opposite ends. In every iteration of the while loop, we calculate the area in O(1) constant time, and then we strictly move one pointer inwards (l += 1 or r -= 1). The pointers will meet exactly after n - 1 steps.
  • Space Complexity: O(1). We only track three integer variables (l, r, and best). No matter how large the array of heights gets, our memory usage remains constant.

Edge cases ​

  • Two lines: The absolute minimum input size is 2 (e.g. [1, 1]). The loop runs exactly once, calculates the area, and returns.
  • Zeros: [0, 2, 0]. The area formula handles zeros gracefully: min(0, 0) * 2 = 0. Water height is perfectly zero.
  • A massive spike in the middle: [1, 100, 100, 1]. The pointers start at 1 and 1, calculate an area of 1 * 3 = 3, then move inwards to discover the 100s and update the area to 100 * 1 = 100.

The mistake worth naming ​

The tempting wrong rule is move whichever pointer will give the taller next wall, or always move the left one. Both are wrong, and both pass small test cases.

The correct rule comes from the argument above, not from intuition about heights. If you cannot state why discarding an element is safe, you do not have a two-pointer solution — you have a guess that happens to pass.

Where this goes next ​

  • Trapping Rain Water — looks similar and is genuinely harder, because you measure the water above each individual position rather than one container. It is 4.5.5 and it uses the same "the shorter side is the bottleneck" insight in a different way.
  • Largest Rectangle in Histogram — bars are solid rather than thin lines, so the answer needs a monotonic stack instead. 4.8.

The rule: when the answer is capped by a minimum or a maximum of two ends, the limiting end is the one to discard.

What the interviewer will push on ​

"Prove that moving the shorter line is correct." The full argument above: width always shrinks, and moving the taller line cannot raise the height, so those containers are all strictly worse.

"What if the two heights are equal?" Either move is fine, for the reason given above.

"Why does this not need sorting?" Because the rule comes from geometry, not from order. Sorting would destroy the positions, and the positions are the width.

One thing to volunteer: state the area formula before writing any code, and point out that the height is the min. Half of all wrong solutions to this problem come from using the wrong height.

Next: 4.5.5 Trapping Rain Water — the hardest problem in this group, and the one where the two-pointer version needs a real proof.