Skip to content
LEETFLIX

Container With Most Water

MediumArrayTwo pointersGreedy
Solve on LeetCode

Two pointers with a proof. The step that looks like a guess is actually airtight.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

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, such that the container contains the most water. Return the maximum amount of water a container can store.

Constraints

  • —n == height.length
  • —2 <= n <= 10^5
  • —0 <= height[i] <= 10^4

Examples

Input

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

Output

49

height

10816223544586377849▲l▲r

The lines at index 1 (height 8) and index 8 (height 7) are 7 apart; the water level is capped by the shorter one: 7 × 7 = 49.

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Two pointers from the outside in

Measure the current container, then move the pointer at the shorter wall inward.

Widest first. At each step compute the area, keep the best, and retire the shorter wall — it can never be part of a better container.

Algorithm

  1. l = 0, r = n − 1, best = 0.
  2. While l < r: area = (r − l) × min(h[l], h[r]), best = max(best, area).
  3. If h[l] < h[r] then l += 1, else r −= 1.
  4. Return best.
Time
O(n)
Space
O(1)
Solution.py
class Solution:    def maxArea(self, height: list[int]) -> int:        l, r = 0, len(height) - 1        best = 0        while l < r:            area = (r - l) * min(height[l], height[r])            best = max(best, area)            if height[l] < height[r]:                l += 1  # the left wall can never do better; retire it            else:                r -= 1  # the right wall can never do better; retire it        return best
Watch this run

03

Interactive walkthrough

Playing “Two pointers from the outside in”. Edit the input, hit Run, then scrub.

Approach: Two pointers from the outside in

Loading animation…

Up next

#1Two Sum

Easy

Python · Go · Animated

#121Best Time to Buy and Sell Stock

Easy

Python · Go · Animated