Each number is the height of a bar, one unit wide. After it rains, how much water is trapped between the bars?
DSA Animator › DSA Revision › Arrays › Trapping Rain Water
Remember: water at a bar is the smaller of the two tallest walls, minus the bar. With two pointers, the lower side is already decided. The video solves Trapping Rain Water (LeetCode 42, Hard) with the Two Pointers pattern from the Arrays topic, and you can replay every step in the interactive Trapping Rain Water animation.
Each number is the height of a bar, one unit wide. After it rains, how much water is trapped between the bars?
For these twelve bars, six units of water are trapped.
For each bar, you could scan left and right for the tallest walls, which is O of n squared. Water above a bar is the smaller of the tallest wall on its left and on its right, minus its own height.
Use two pointers, and keep the tallest wall seen from each side. Whichever side has the lower bar is already decided, because the other side is at least as tall. So settle that side: add its water, and move it inward.
The left side is lower, so it moves: index 2 sits under a left wall of 1, and traps 1 unit. Later the right side is lower: index 9 sits under a right wall of 2, and traps 1 unit. Back on the left, indexes 4, 5 and 6 sit under a left wall of 2, and trap 1, 2 and 1 units. The pointers meet at the tallest bar, and the total is 6.
In code, if the left bar is lower, update the left maximum, add left max minus the height, and move left. Otherwise do the same on the right. Each bar is visited once, so it's O of n time and O of 1 space.
Remember: water at a bar is the smaller of the two tallest walls, minus the bar. With two pointers, the lower side is already decided.