Trapping Rain Water

Water over each bar is bounded by the smaller of the tallest walls to its left and right. Two pointers advance from the shorter side, where the bounding max is known.

Category: Two Pointers
Time complexity: O(n)
Space complexity: O(1)

Pseudocode

lo, hi at both ends
advance the side with the shorter bar
  add (runningMax − height) to water
until pointers meet

Reference implementation

while lo &lt; hi:
    if a[lo] &lt; a[hi]:
        lMax = max(lMax, a[lo])
        water += lMax - a[lo]; lo += 1
    else:
        rMax = max(rMax, a[hi])
        water += rMax - a[hi]; hi -= 1

Open the interactive Trapping Rain Water visualisation →