• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10⁵

Trapping rain water is fundamentally a challenge of determining the water level above each elevation bar. The water level at any index is limited by the tallest wall to its left and the tallest wall to its right. Specifically, the amount of water at a given point is the minimum of these two peaks, minus the height of the bar itself.

The most straightforward way to solve this is to iterate through every single bar in the array and, for each one, perform a separate scan to the left and to the right to find the maximum height in both directions. While easy to understand, this repeated scanning leads to an O(N²) time complexity, which is far too slow as the number of bars increases.

# Brute force: scan left and right for every bar
def brute_force(height):
    total = 0
    for i in range(len(height)):
        left_max = max(height[:i+1])
        right_max = max(height[i:])
        total += min(left_max, right_max) - height[i]
    return total

Instead of re-scanning, we can precompute the tallest walls to the left and right for each bar. By creating two arrays to store these maximums, we reduce the time complexity to O(N).

# Intermediate: Dynamic Programming with extra space
def trap_dp(height):
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n
    
    # Precompute left and right maxes
    for i in range(1, n): left_max[i] = max(left_max[i-1], height[i-1])
    for i in range(n-2, -1, -1): right_max[i] = max(right_max[i+1], height[i+1])
    
    water = 0
    for i in range(n):
        level = min(left_max[i], right_max[i])
        if level > height[i]:
            water += level - height[i]
    return water

While this is much faster, it requires O(N) extra space for those auxiliary arrays. We can do even better, though, by using two pointers to calculate these maximums on the fly, eliminating the need for extra memory entirely.

The bottleneck is always the shorter of the two boundary walls. We don't need to know the absolute tallest wall in the entire array—we only need to know that there exists some wall on the left and some wall on the right that are taller than our current position. By using two pointers starting from both ends, we can maintain the running maximums (leftMax and rightMax) on the fly, eliminating the need to look ahead or behind.

We use two pointers, l and r. We keep track of l_max and r_max. At each step, we compare the heights of the walls at the two pointers. Because we know the shorter side is limited by its own current max, we can safely calculate the water trapped at the shorter pointer and advance it inward, knowing that the water level is constrained by the maximum wall we have already seen on that side.

# Optimal: two pointers
def trap(height):
    l, r = 0, len(height) - 1
    l_max, r_max, water = 0, 0, 0
    while l < r:
        if height[l] < height[r]:
            l_max = max(l_max, height[l])
            water += l_max - height[l]
            l += 1
        else:
            r_max = max(r_max, height[r])
            water += r_max - height[r]
            r -= 1
    return water