Two Pointers
LC #11Medium
Container With Most Water
Two Pointers
AmazonGoogleMetaBloombergProblem
Find two lines that together with the x-axis form a container that holds the most water.
arraytwo-pointersgreedy
Constraints
- ›2 ≤ n ≤ 10⁵
- ›0 ≤ height[i] ≤ 10⁴
Example
Input
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]Output
49Why
Lines at index 1 (h=8) and 8 (h=7): min(8,7) × (8−1) = 7 × 7 = 49