#6MediumTwo Pointers· Opposite Direction Pointers

Container With Most Water

You are given an array `height` where `height[i]` is the height of a vertical wall standing at x-coordinate `i`. Pick any two walls. Together with the x-axis they form a container, and the water it holds is `min(height[i], height[j]) * (j - i)`. Return the largest amount of water any pair of walls can hold. The container cannot be tilted, and walls between the chosen pair do not affect the result.

Input format

height: array of non-negative integers

Output format

Integer: the maximum water area

Examples

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

Output: 20

Walls at index 1 (height 5) and index 5 (height 6) hold min(5, 6) * 4 = 20.

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

Output: 16

The two outer walls of height 4 are 4 apart: 4 * 4 = 16.

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

Output: 9

The two tall walls are adjacent (9 * 1 = 9); the outer pair only gives 1 * 3 = 3.

Constraints

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

Study first

Arrays & Contiguous Memory

#two-pointers
#greedy
#arrays