Problem

Container With Most Water

LeetCode #11Medium
Pick two lines that hold the most water

Given heights representing vertical lines, pick two lines that together with the x-axis form a container holding the most water, and return that maximum area.

Asked atAmazonGoogleMeta
1
2
3
4
5
6
7
8
1
8
6
2
5
4
8
3
7
[0][1][2][3][4][5][6][7][8]
Brute force
▸
1given heights[]
2max ← 0
3for i ← 0 to n − 2:
4    for j ← i + 1 to n − 1:
5        area = (j − i) × min(h[i], h[j])
6        if area > max: max ← area
7return max
state
  • n9

line 1We want two lines that, with the x-axis, hold the most water. area = (j − i) × min(h[i], h[j]).

Container with most Water, animated walkthrough (Array sheet)