Skip to main content
DSA patterns

Container With Most Water

mediumTwo pointersMetaGoogleSwiggy

Problem statement

You're given an array height where height[i] is the height of a vertical line standing at position i. Pick any two of these lines — together with the x-axis, they form a container. Find the two lines that hold the most water, and return that amount.

The water a container holds is limited by its shorter line (water spills over the shorter side) times the distance between the two lines. Picture this as picking two servers from a row, where each server's "height" is its free capacity, and you want the widest, tallest matching pair to size a buffer between them — the pair's usable size is capped by whichever of the two is smaller.

Examples

Example 1

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

Output: 49

Explanation: The lines at index 1 (height 8) and index 8 (height 7) are 7 apart. The container is limited by the shorter line, height 7, so it holds 7 * 7 = 49 units of water — the largest amount any pair in this array can hold.

Example 2

Input: height = [1, 1]

Output: 1

Explanation: There's only one possible pair, at distance 1 apart with both heights equal to 1, giving 1 * 1 = 1.

Hints

Hint 1: Checking every pair of lines works, but with up to 10^5 lines, that's up to about 5 billion comparisons — far too slow.

Approach

Optimal: Two pointers

Intuition

Start as wide as possible: one pointer at the first line, one at the last. That width can only shrink from here, so the only way to ever find something bigger is to look for a taller limiting line — and the limiting line is always the shorter of the two current lines. Moving the taller line inward keeps the same short side and only loses width, so it can never help. Moving the shorter line, though, might find a taller line and make up for the lost width. So always move the shorter side inward, and keep the best area seen along the way. This is what turns the brute force's full pairwise scan into a single pass.

Steps

  1. Set left = 0 and right = n - 1.
  2. Track best = 0.
  3. While left < right:
    • Compute width = right - left.
    • If height[left] < height[right], this pair's area is width * height[left]; update best if it's larger, then move left one step right.
    • Otherwise, this pair's area is width * height[right]; update best if it's larger, then move right one step left.
  4. Return best.

Dry run

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

left right height[left] height[right] width area move best
0 8 1 7 8 8 left (shorter) 8
1 8 8 7 7 49 right (shorter) 49
1 7 8 3 6 18 right (shorter) 49
1 6 8 8 5 40 right (equal, move either) 49
1 5 8 4 4 16 right (shorter) 49
1 4 8 5 3 15 right (shorter) 49
1 3 8 2 2 4 right (shorter) 49
1 2 8 6 1 6 right (shorter), left==right next, loop ends 49

The best area found, 49, matches the example — and it's found without ever checking most of the pairs the brute force would.

Edge cases: an array of exactly two lines still works, since the loop runs once before left meets right; when several lines tie for tallest, moving either pointer is safe because both sides are equally limiting.

Complexity

Time O(n) - the two pointers start at opposite ends and move toward each other; each step moves exactly one pointer inward, so the whole scan is a single O(n) pass.

Space O(1) - just two index variables and a running best value, no matter how large the input is.

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        best = 0
        while left < right:
            width = right - left
            if height[left] < height[right]:
                best = max(best, width * height[left])
                left += 1
            else:
                best = max(best, width * height[right])
                right -= 1
        return best


if __name__ == "__main__":
    print(Solution().maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
    print(Solution().maxArea([1, 1]))  # 1
RecapThe whole problem in a few lines, for the night before
  • Spot it: pick two lines to hold the most water; area = width x shorter height
  • Idea: start with pointers at both ends and move the pointer at the shorter line inward; moving the taller one can never help
  • Cost: O(n) time, O(1) space
  • Trap: the height is the shorter of the two lines, not the taller

Interview follow-ups

  • What if you needed to return the pair of indices that gives the maximum area, not just the area?

    Keep two extra variables (bestLeft, bestRight) alongside best, and update them at the same time you update best inside the loop. No change to the time or space complexity — it's still O(n) time and O(1) extra space, just two more variables to track.

  • The heights arrive as a stream and you can't store the whole array — can you still find the max area?

    Not with the two-pointer approach as written, since it needs random access to both ends at once. One option is a two-pass streaming approach: first pass computes the maximum height seen so far from the left and stores enough summary state; more practically, if only an approximate or windowed answer is acceptable, track a bounded set of the tallest lines seen recently (similar to a sliding-window maximum) and pair candidates from that set, trading exactness for bounded memory.

Frequently asked questions

The container's height is always capped by the shorter of the two lines. If you move the taller line inward, the shorter line — and therefore the cap on the height — stays exactly the same, while the width strictly shrinks. So the area can only get smaller or stay the same, never improve. Moving the shorter line is the only move that has a chance of finding a taller limiting line to make up for the lost width.

Picking the best-matching pair from two ends of a sorted or ordered range — capped by whichever side is the bottleneck — is the same shape as sizing a connection pool or buffer between two capacity limits, or matching a pair of nodes from a ranked list where the weaker one sets the ceiling. It's also a standard way interviewers check whether a candidate can spot a two-pointer opportunity and justify, with a real argument, why a pointer never needs to move backward — not just apply the pattern by memory.

No — every line eventually gets compared as either the current left or right at some point before the pointers cross it, because the pointer that moves is always the shorter one, and it only ever moves one step at a time, in one direction. The line that stays in place (the taller one) keeps being compared against every new position the other pointer reaches, so it's checked against the whole remaining range before it's ever passed over.

The problem's constraints guarantee height[i] >= 0, so this never comes up here, but if it did, the same two-pointer logic still works — width and the "move the shorter side" rule don't depend on heights being non-negative, only the interpretation of "water held" would need heights clamped to max(height[i], 0) first, since a container can't hold negative water.