Container With Most Water

The key idea

Start with the widest container (both ends) and shrink inward. The shorter line caps the area, so moving the taller line can never help — only moving the shorter line gives a chance at more water. This greedy move lets two pointers cover all useful pairs in one pass.

Problem

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.

The area between line left and line right is min(height[left], height[right]) * (right - left) — the shorter line caps the height and the index distance is the width. Note that you may not slant the container.

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

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

Input: height = [4,3,2,1,4] Output: 16

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →