You are given an integer array height where height[i] is the height of a vertical line standing at position i. Pick the two lines that, together with the x-axis, hold the most water: the area is the distance between them times the shorter line. Return that maximum area. The container cannot lean.
Examples
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: the lines at positions 1 and 8 give min(8,7) * 7 = 49.
Example 2:
Input: height = [1,1]
Output: 1
Example 3:
Input: height = [4,3,2,1,4]
Output: 16
Example 4:
Input: height = [1,2,1]
Output: 2
Constraints
2 <= height.length <= 10^5
0 <= height[i] <= 10^4
Prerequisites
Two pointers — one pass with an index at each end, and the argument for why moving one of them cannot lose the answer.
How to think about it
1. Two Pointers From the Ends Optimal
Intuition
Start as wide as possible, because width is at its maximum and can only shrink. From there the only way to do better is a taller limiting side — so move the pointer at the SHORTER line. Moving the taller one keeps the same short side and loses width, which can never help; being able to say that sentence is the whole problem.
Algorithm
1. Put pointers at both ends and track the best area seen. 2. Area is the distance between them times the shorter height. 3. Move the pointer at the shorter line inward. 4. Stop when they meet.
Time & Space
Time O(n) — one pass. Space O(1). The brute force over all pairs is O(n^2), which this replaces with the argument above.