Hints — p55 Trapping Rain Water

Hint 1. For each column i, water above it = min(tallest_wall_to_the_left, tallest_wall_to_the_right) - height[i] (clipped at 0). Summing this is the entire problem.

Hint 2. Brute is “for each i, scan left and right for max” — O(n²). To get O(n), precompute max_left[i] and max_right[i] arrays in two passes. Then one pass to sum.

Hint 3. Can you drop the arrays? Yes — two pointers converging from both ends. Maintain lmax and rmax. The key insight: whichever side has the SHORTER current bar is the bottleneck on its side, so water at that pointer’s column = that_side_max - height[pointer]. Move that pointer inward.

Hint 4. A third O(n) approach exists: monotonic decreasing stack. Instead of summing vertical columns, sum horizontal slices. When a tall bar arrives and pops a shorter one, the popped bar is the floor of a slice bounded by the bar below it on the stack (left wall) and the current bar (right wall).

Hint 5. Stack version pitfalls: (a) check if not stack: break AFTER popping — the popped bar may have no left wall, no slice exists. (b) width = i - left - 1 (subtract one for the popped index itself, one because endpoints are exclusive). (c) bounded_height = min(current, height[left]) - height[bottom].

If still stuck: see solution.py.