Trapping Rain Water

For each index, the water it can hold equals min(maxLeft, maxRight) - height[i]. Precompute these maximums in two arrays — one scanning left-to-right and one right-to-left.

1. 1Build maxLeft[i] = max height from index 0 to i.
2. 2Build maxRight[i] = max height from index i to n-1.
3. 3For each index, add min(maxLeft[i], maxRight[i]) - height[i] to result.

Why it's not optimal: Uses O(n) extra space for the two arrays. Two pointers maintain these maximums on the fly in O(1) space.

def trap(height):
    n = len(height)
    maxL = [0] * n
    maxR = [0] * n
    maxL[0] = height[0]
    for i in range(1, n):
        maxL[i] = max(maxL[i-1], height[i])
    maxR[n-1] = height[n-1]
    for i in range(n-2, -1, -1):
        maxR[i] = max(maxR[i+1], height[i])
    return sum(min(maxL[i], maxR[i]) - height[i] for i in range(n))

Instead of precalculating the maximum left and right heights for every index (which takes O(n) space), we can maintain these maximums dynamically using two pointers moving inwards.

1. 1Initialize L and R pointers at the ends, and track maxL and maxR.
2. 2If maxL < maxR, the trapped water at L is strictly strictly bounded by maxL. Update maxL and add maxL - height[L] to result. Move L forward.
3. 3Otherwise, do the same symmetrically for the right side, updating maxR and moving R backwards.