Trapping Rain Water — Interview Guide

• Water above a bar is bounded by the min of the tallest bars to its left and right.
• Two pointers exploit that the trapped water at each end depends only on the shorter boundary.
• A monotonic decreasing stack also solves it by matching basins.

def trap(h):
    l, r = 0, len(h) - 1
    left_max = right_max = water = 0
    while l < r:
        if h[l] < h[r]:
            left_max = max(left_max, h[l])
            water += left_max - h[l]
            l += 1
        else:
            right_max = max(right_max, h[r])
            water += right_max - h[r]
            r -= 1
    return water

• 2D trapping rain water on a 2D height map (BFS from borders).
• Return the indices of the bars that actually hold water.
• Handle a terrain with a single global slope.