Container With Most Water

Medium Two Pointers

You are given a list height where height[i] is the height of a vertical line at position i. Pick two lines that, with the x-axis, form a container. Return the maximum water it can hold — the area is width * min(two heights).

Examples

Input:  [1,8,6,2,5,4,8,3,7]
Output: 49     # lines at index 1 (h=8) and index 8 (h=7): width 7 * min(8,7) = 49

Input:  [1,1]
Output: 1

Constraints

2 <= len(height) <= 10^5
0 <= height[i] <= 10^4

Solution

Approach strategy: Brute force tries all pairs: O(n^2). Instead put pointers at both ends (the widest possible container) and greedily shrink.

Full worked solution, code, and complexity analysis available in the interactive view.

Container With Most Water

Examples

Constraints

Solution

Related problems