Container With Most Water

Medium · Two Pointers

You are given an array of non-negative integers where each value represents the height of a vertical line drawn at that index on a number line. Choose two of these lines that, together with the x-axis, form a container, and return the maximum amount of water it can hold. The water held is determined by the shorter of the two chosen lines multiplied by the distance between their indices.

Examples

Input:  height = [1,8,6,2,5,4,8,3,7]
Output: 49
Why:    Lines at index 1 (height 8) and index 8 (height 7) give area min(8,7)*(8-1)=49, the best possible.

Input:  height = [1,1]
Output: 1
Why:    Only one pair exists: min(1,1)*(1-0)=1.

Input:  height = [4,3,2,1,4]
Output: 16
Why:    The two end lines both have height 4 and are 4 apart, giving 4*4=16.

Constraints

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

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Container With Most Water

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Container With Most Water. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.