Challenge: trapping rain water

Calculate the total water trapped between bars in O(n) time and O(1) space using a two-pointer approach.

Optional challenge. These puzzles have efficiency checks built into the test suite, so brute-force solutions are rejected deterministically — no timing involved.

Given an array of non-negative integers representing bar heights in a histogram, return the total amount of water that can be trapped between the bars after rain. trap([0,1,0,2,1,0,1,3,2,1,2,1]) → 6.

The naive approach — for each bar, find the tallest bar to its left and right, then compute how much water sits above it — is O(n²) or O(n) with precomputed prefix/suffix arrays using O(n) space. There is a way to do it in O(n) time and O(1) space.

Hint: use two pointers starting at both ends. Track the maximum height seen from the left so far and from the right so far. At each step, process the side with the smaller maximum — water above that bar is bounded by the smaller of the two maxima, and you already know the smaller one.

Trapping rain waterPython

Write trap(height) returning the total water trapped. Aim for O(n) time and O(1) space using two pointers.

trap([0,1,0,2,1,0,1,3,2,1,2,1]) → 6trap([3,0,0,2,0,4]) → 10

Finished reading? Mark it complete to track your progress.