Container With Most WaterMedium

Container With Most Water

Medium 29.4k56% acceptance

ArrayTwo PointersGreedy

You are given an array height of n non-negative integers, where each value is the height of a vertical line drawn at that x-position. Pick two lines that, together with the x-axis, form a container holding the most water, and return that maximum area.

The area between lines i and j is min(height[i], height[j]) × (j − i). The container cannot be tilted.

Example 1

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

Output: 49

Lines at index 1 (height 8) and index 8 (height 7) span 7 units: min(8,7)·7 = 49.

Example 2

Input: height = [1,1]

Output: 1

min(1,1)·1 = 1 — the only pair available.

Constraints

2 ≤ height.length ≤ 10⁵
0 ≤ height[i] ≤ 10⁴

Asked atAmazonMetaGoogleBloomberg

JavaScript

⌘↵ to run

Loading editor…

Case 1

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

expected: 49

Case 2

[1,1]

expected: 1

Case 3

[4,3,2,1,4]

expected: 16

Case 4

[1,2,1]

expected: 2

Case 5

[2,3,4,5,18,17,6]

expected: 17

Case 6

[0,0]

expected: 0