Visualize

Pattern visualizer

Container With Most Water

Start with the widest possible container and walk the two walls toward each other. Water is capped by the SHORTER wall, so moving the taller one can never help — width shrinks and the cap stays. Moving the shorter wall is the only move that might find something taller, which is why one pass safely covers every candidate pair. Animated on: Walls of heights [1, 8, 6, 2, 5, 4, 8, 3, 7] — pick the two that trap the most water: area = width × shorter wall..

Opposite-ends two pointers — always move the shorter wall

time O(n)space O(1)step 1 / 12
1
[0]
8
[1]
6
[2]
2
[3]
5
[4]
4
[5]
8
[6]
3
[7]
7
[8]
line 2

Walls at both ends: l on height 1, r on height 7. Width 8 is the widest any container will ever be — from here width only shrinks, so every move must gamble on finding a taller wall.

Pseudocode
1FUNCTION maxArea(height):
2  set l to 0, r to (length of height) - 1, best to 0
3  WHILE l < r:
4    area = (r - l) * the shorter of height[l] and height[r]
5    best = the larger of best and area
6    IF height[l] < height[r]: move l one step right
7    ELSE: move r one step left
8  RETURN best

← / → step · space play · Home restart

Where to practice Arrays

Practice Arrays problemsAll Arrays problemsBack to roadmap