Trapping Rain Water

Solution

Solutions evolve from squared to linear runtime, and from multiple to single iteration.

Brute Force (TLE)

Sum the water heights for each index.

Complexity

time: $O(n^2)$
space : $O(1)$

def trap(self, height: List[int]) -> int:
    res = 0
    n = len(height)

    for i in range(n):
        # calc the max height to the left
        left_max = 0
        for l in range(i):
            left_max = max(left_max, height[l])

        # calc the max height to the right
        right_max = 0
        for r in range(i+1, n):
            right_max = max(right_max, height[r])

        # calc the water height
        water = min(left_max, right_max) - height[i]
        if water > 0: res += water

    return res

DP

Initialize leftMax[0] = height[0] and rightMax[n-1] = height[n-1].

• For $1 \le i \le n-1$, leftMax[i] = max(leftMax[i-1], height[i])
• For $0 \le i \le n-2$, rightMax[i] = max(rightMax[i+1], height[i])

Complexity

time: $O(n)$
space : $O(n)$

def trap(self, height: List[int]) -> int:
    n = len(height)
    prefix_max = [0 for _ in range(n)]
    suffix_max = [0 for _ in range(n)]
    curr_prefix_max = 0
    curr_suffix_max = 0
    res = 0
    
    for i in range(n):
        curr_prefix_max = max(curr_prefix_max, height[i])
        prefix_max[i] = curr_prefix_max

    for j in reversed(range(n)):
        curr_suffix_max = max(curr_suffix_max, height[j])
        suffix_max[j] = curr_suffix_max

    for k in range(n):
        curr_water = min(prefix_max[k], suffix_max[k]) - height[k]
        res += curr_water

    return res

Monotonic Stack

stack stores the indices of height in descending order of temperature from bottom to top. If we found a bar longer than that at the top, we are sure that the bar at the top of the stack is bounded by the current bar and a previous bar in the stack, hence, we can pop it and add resulting trapped water to res.

Complexity

time: $O(n)$ (each bar can be operated at most twice: inserted to and removed from the stack)
space : $O(n)$

def trap(self, height: List[int]) -> int:
    res = 0
    n = len(height)
    stack = []
    for i in range(n):
        while stack and height[i] > height[stack[-1]]:
            top = stack.pop()
            # will need stack[-1] for the left bar
            if not stack:
                break
            distance = i - stack[-1] - 1
            bounded_height = min(height[i], height[stack[-1]]) - height[top]
            res += distance * bounded_height
        stack.append(i)
    return res

Two Pointers

Use left and right to traverse from ends to middle.

Complexity

time: $O(n)$
space : $O(1)$

def trap(self, height: List[int]) -> int:
    n = len(height)
    prefix_max = 0
    suffix_max = 0
    lo, hi = 0, n - 1
    res = 0
    while lo <= hi:
        prefix_max = max(prefix_max, height[lo])
        suffix_max = max(suffix_max, height[hi])
        if prefix_max < suffix_max:
            res += prefix_max - height[lo]
            lo += 1
        else:
            res += suffix_max - height[hi]
            hi -= 1
    return res