noodleProblems/
Container With Most Water
#21

Container With Most Water

AlgorithmmediumArrayTwo PointersGreedy

You are given an integer array height of length n. Each value height[i] is a vertical line drawn from (i, 0) to (i, height[i]).

Pick two of these lines so that, together with the x-axis, they form a container holding the most water. Return that maximum amount of water.

The container's area is min(height[i], height[j]) * (j - i) for the chosen pair i < j — the shorter line caps the water level, and the horizontal distance sets the width. The container cannot be tilted.

Example cases

  • classic
    in height = [1,8,6,2,5,4,8,3,7]
    out 49
    Lines at index 1 (height 8) and index 8 (height 7) give min(8, 7) * (8 - 1) = 7 * 7 = 49.
  • two lines
    in height = [1,1]
    out 1
    Only one pair: min(1, 1) * (1 - 0) = 1.
  • tall ends win
    in height = [2,3,4,5,18,17,6]
    out 17
    Indices 4 and 5: min(18, 17) * (5 - 4) = 17.

Constraints

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4
Saved
height =
[1,8,6,2,5,4,8,3,7]