Pattern visualizer
Trapping Rain Water
Water above any bar rises to min(tallest wall on its left, tallest wall on its right) minus its own height. Instead of precomputing those walls, two pointers walk inward and always settle the side whose CURRENT bar is shorter — the opposite end's tall bar guarantees the other side can't be the bottleneck, so one running leftMax (or rightMax) decides each cell's water on the spot. Animated on: Given elevations [4, 2, 0, 3, 2, 5], compute how much rain water is trapped between the bars..
Two pointers with running wall maxes
time O(n)space O(1)step 1 / 13
4
[0]2
[1]0
[2]3
[3]2
[4]5
[5]line 2
Six bars: [4,2,0,3,2,5]. Park l on the first bar (4) and r on the last (5). leftMax/rightMax remember the tallest wall seen from each side; water starts at 0.
Pseudocode
1To find how much water is trapped:2 put a left marker on the first bar and a right marker on the last; leftMax, rightMax and water all start at 03 keep going while the left marker is before the right marker:4 if the left bar is shorter than the right bar:5 raise leftMax to whichever is taller: leftMax or the left bar6 add (leftMax minus the left bar) to water, then move the left marker one step right7 otherwise:8 raise rightMax to whichever is taller: rightMax or the right bar9 add (rightMax minus the right bar) to water, then move the right marker one step left10 the answer is the total water collected
← / → step · space play · Home restart