Trapping Rain Water

Every bar in this elevation map has water above it. You can see the water. Computing how much water sits above each bar seems straightforward. The formula is simple. The execution is not.

For each bar, scan left to find maxLeft, scan right to find maxRight. Water above bar i is min(maxLeft, maxRight) - height[i]. Tap bars to scan them and see what each scan costs.

FIG. 1 — THE OVERLAPPING SCANS
— every bar's left+right walk re-reads the same neighbors —

There are 12 bars. To compute water for ALL of them using per-bar scanning, how many total scan operations will it take?