DSAPrep
MediumTwo Pointers

Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container that holds the most water.

Return the maximum amount of water a container can store. Notice that you may not slant the container.

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) form the container: width = 8 - 1 = 7, height = min(8,7) = 7, area = 49.

Example 2

Input: height = [1,1]
Output: 1

Constraints

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4
View original on LeetCode ↗

The area between two lines is width * min(height of the two lines) — it’s always capped by the shorter line. That single fact is what lets us skip most pairs without checking them.

Brute Force

Time O(n²)Space O(1)

Check every pair of lines and keep the best area.

class Solution:
    def maxArea(self, height: list[int]) -> int:
        best = 0
        n = len(height)
        for i in range(n):
            for j in range(i + 1, n):
                width = j - i
                area = width * min(height[i], height[j])
                best = max(best, area)
        return best

Correct but checks all n²/2 pairs, including many that can’t possibly beat the current best.

Two Pointers

OptimalTime O(n)Space O(1)

Start with the widest possible container: pointers at both ends. At each step, the shorter of the two lines is the bottleneck — moving the taller pointer inward can only shrink the width without ever increasing the limiting height, so it can never help. Moving the shorter pointer inward is the only move that has a chance of finding a taller line and a bigger area. So: always move the pointer at the shorter line.

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

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

L
1
0
8
1
6
2
2
3
5
4
4
5
8
6
3
7
R
7
8
area = 8best = 8
1 / 5
comparingresult

width=8, min(1,7)=1, area=8. Left is shorter → move L.

Why we never miss the true answer: suppose the optimal pair is (i, j). While scanning, whichever of left/right reaches the shorter boundary of the true answer first, the algorithm is forced to move only the other pointer past it — but every pair involving an index outside [i, j] on the discarded side is provably worse (smaller width and capped by the same or shorter height), so nothing optimal is ever skipped.

Complexity: the pointers move toward each other and the loop ends when they meet → O(n) time, O(1) space.