Container With Most Water
Medium· opposite ends· greedy elimination
Problem
Each element of an array is the height of a vertical line at that position. Pick two lines that, together with the x-axis, hold the most water, and return that amount. The amount is the distance between the lines times the shorter of the two heights.
Examples
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Lines at index 1 (height 8) and index 8 (height 7) give 7 * 7 = 49.
Input: height = [2,2]
Output: 2
Constraints
- • 2 <= height.length <= 10^5
- • 0 <= height[i] <= 10^4
Hints & approach
Hint 1
Start with the widest possible container.
Hint 2
Moving the taller line inward can never help. Why?
Hint 3
Always move the pointer at the shorter line.
Approachtry the hints first
Start with pointers at both ends and compute the area. The shorter line limits the height, and any container that keeps it while narrowing the width can only be smaller, so that line can be discarded. Move the pointer at the shorter line inward and repeat, tracking the maximum area. The pointers meet after n - 1 steps.
Time O(n) · Space O(1)