Container With Most Water
MediumPick two lines that hold the most water
Water held = width × the shorter wall; start with the widest gap and always move the shorter wall inward.
The idea
Area is width × the shorter of the two walls. Start as wide as possible and always move the shorter wall inward — it's the only move that could ever increase the area.
The trick
- Moving the taller wall can never help: width shrinks and height is still capped by the shorter wall.
1
8
6
2
5
4
8
3
7
0
1
2
3
4
5
6
7
8
Step 1 of 38. Brute force: measure water for every pair of walls. Values: 1, 8, 6, 2, 5, 4, 8, 3, 7.
1/38
Brute force
timeO(n²)spaceO(1)
Every pair of walls.
1// measure water for every pair of walls2for (let i = 0; i < n; i++)3 for (let j = i + 1; j < n; j++)4 best = Math.max(best, (j - i) * Math.min(h[i], h[j]));Input
- array
- [1, 8, 6, 2, 5, 4, 8, 3, 7]
Memory
- i
- —
- j
- —
- area
- —
- pairs tried
- —
Output
- area
- —
- best
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
- Output:
- 49
- Explanation:
- The lines at 8 and 7 hold the most water.
Example 2
- Input:
- height = [1, 1]
- Output:
- 1
- Explanation:
- Width 1, height 1 → area 1.
Example 3
- Input:
- height = [4, 3, 2, 1, 4]
- Output:
- 16
- Explanation:
- The two 4s at the ends give area 16.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.