You are given a list height of n non-negative integers. Picture a vertical wall at each
position i, height[i] units tall, with neighbouring walls one unit apart.
Choose two walls. With the ground they form a tank: its width is the distance between the two walls, and the water can rise only as high as the shorter of them. The walls in between don't get in the way. Return the most water (width × the shorter height) that any pair of walls can hold.
Example 1
- Input
- height = [2, 7, 4, 8, 3, 6]
- Output
- 24
Example 2
- Input
- height = [1, 1]
- Output
- 1
Constraints
heightholds 2 to 10⁵ numbers.- Every height is between 0 and 10⁴.
Show the pattern
Two pointers
The water level is capped by the shorter wall, so moving the taller wall inwards can never help. Two pointers that always move the shorter wall check every pair that could win, in one pass.
See two pointers in a visualiserShow the approach
Start with left = 0 and right = n − 1, the widest tank, which holds
(right − left) × min(height[left], height[right]). Now move the shorter of the two walls
inwards. Any other tank that uses the shorter wall would be narrower, and its level would still be
at most that wall's height, so none of them can beat the current one: that wall is done with.
Keep the best amount seen and repeat until the walls meet. (When the two are equally tall, moving
either is safe.)
Time: O(n) · Space: O(1)