Container With Most Water LeetCode 11

LeetCode 11 gives you an integer array height of length n. Each value height[i] represents a vertical line at x-coordinate i. You must choose two lines that, together with the x-axis, form a container holding the most water. The area of the container formed by lines i and j (where i < j) is: area = min(height[i], height[j]) * (j - i). Water spills over the shorter line, so the minimum height is the limiting factor.

The problem looks deceptively simple — just two nested loops, right? For small inputs yes, but n can be up to 100,000, so the brute-force O(n^2) approach will time out. The challenge is finding the optimal pair in a single linear pass.

Key constraints to keep in mind going into your solution design:

The straightforward solution is two nested loops: for every pair (i, j) where i < j, compute area = min(height[i], height[j]) * (j - i) and track the running maximum. This is O(n^2) time and O(1) space.

For n = 100,000 this means up to 5 billion pair evaluations — roughly 5 to 10 seconds at typical processor speeds, well beyond any judge's time limit. Interviewers want you to name the brute force, explain its flaw, and then derive the linear solution.

The brute force is a valid starting point in a conversation. State it, prove it correct by exhaustion, then ask: "Is there a way to prune pairs we know cannot be optimal?" That question leads directly to the two-pointer insight.

Initialize two pointers: left = 0 (leftmost line) and right = n - 1 (rightmost line). This starting position gives the maximum possible width. Compute the area for this pair and record it as the running maximum.

At each step, move the pointer pointing to the shorter line one step inward. If both lines are equal height, move either pointer — it does not matter which (both are safe). Repeat until left and right meet.

Every iteration evaluates exactly one pair and advances one pointer, so the total iterations are at most n - 1. Time complexity O(n), space complexity O(1). The entire core logic fits in five lines.

Why is it safe to discard the current shorter pointer and all pairings it has with indices between left and right? Suppose height[left] <= height[right]. Every pair (left, k) where left < k < right has width (k - left) < (right - left) and is still bounded by height[left] on the left. So area(left, k) <= height[left] * (k - left) < height[left] * (right - left) <= area(left, right). None of these inner pairs can beat the area we just recorded for (left, right).

Therefore we can safely advance left inward — every pair involving the old left value with any right-side index smaller than current right is already dominated. We have not skipped the optimal pair; we have proven it cannot use the current left. By symmetry, the same argument applies when height[right] is the shorter side.

This continues until left and right converge, having evaluated exactly the set of pairs that could have been optimal. No brute-force enumeration required.

Students often ask: why not move the taller pointer? Here is the direct argument. If we move the taller pointer inward, the new width is strictly smaller. The height of the new container is min(height[new_left_or_right], height[other]) which is at most the same height as before (bounded by the shorter side that did not move). So the area can only stay the same or decrease — we gain nothing.

Moving the shorter pointer is the only move that gives the area a chance to grow. If the next inward line is taller than the current shorter line, the new height bottleneck rises and might outweigh the width loss. Moving the taller side forecloses that possibility entirely.

Stated differently: the current area is bottlenecked by the shorter line. Eliminating that bottleneck is the only productive action at each step.

Python: def maxArea(height): left, right, best = 0, len(height) - 1, 0 — then while left < right: best = max(best, min(height[left], height[right]) * (right - left)), and if height[left] < height[right]: left += 1, else: right -= 1 — return best. Five lines, O(n) time, O(1) space.

Java: public int maxArea(int[] height) { int left = 0, right = height.length - 1, best = 0; while (left < right) { best = Math.max(best, Math.min(height[left], height[right]) * (right - left)); if (height[left] < height[right]) left++; else right--; } return best; }. Identical logic, different syntax.

Both solutions handle all edge cases uniformly: n = 2 (single iteration), all equal heights, strictly increasing or decreasing arrays. The algorithm does not need special cases because the greedy proof covers all configurations.

Container With Most Water is the canonical "squeeze from both ends" two-pointer problem on unsorted input. Once this pattern clicks, you will recognize its relatives: Trapping Rain Water (LeetCode 42) looks similar but calculates water trapped between all bars — it is a different problem requiring left-max and right-max arrays or a stack.

3Sum (LeetCode 15) sorts the array then uses two pointers on each fixed element, with careful duplicate skipping. Two Sum II (LeetCode 167) uses two pointers on a sorted array with a fixed target. These problems all share the "eliminate one side per step" structure but apply it in different contexts.

The two-pointer family is one of the highest-value patterns to internalize before FAANG interviews. Drill Container With Most Water until the greedy proof feels intuitive — it is the clearest example of why a linear sweep can provably explore all optimal candidates.