Container with the most water

mediumTwo pointers target 25 min

Container with the most water

Not solved yetLeetCode 11. Container With Most Water

A row of vertical walls stands on flat ground, one unit apart. heights[i] is the height of the wall at position i. Pick any two walls. Water poured between them rises to the top of the shorter wall and no higher, because above that it spills over. So the amount of water held by the walls at positions i < j is

(j - i) * min(heights[i], heights[j])

The walls between the two you pick do not matter: ignore them. Return the largest amount of water that any two walls can hold.

Example 1

Inputheights = [2, 5, 4, 1, 6, 3]Output15

The walls at positions 1 and 4 (heights 5 and 6) are 3 apart. The shorter is 5, so they hold 3 × 5 = 15.

Example 2

Inputheights = [3, 1, 2, 4]Output9

The two ends are 3 apart and the shorter is 3: 3 × 3 = 9.

Example 3

Inputheights = [7, 7]Output7

Two walls 1 apart, both 7 tall: 1 × 7 = 7.

Constraints

2 ≤ len(heights) ≤ 10⁵
0 ≤ heights[i] ≤ 10⁴

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern