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:
    if not height: return 0
    res = 0
    n = len(height)
    left_max, right_max = [0 for _ in range(n)], [0 for _ in range(n)]

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

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

    # calc the water height
    for i in range(1, n):
        res += min(left_max[i], right_max[i]) - height[i]
    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:
    res = 0
    n = len(height)
    left, right = 0, n-1
    left_max = right_max = 0
    while left < right:
        # update left_max and right_max
        left_max = max(left_max, height[left])
        right_max = max(right_max, height[right])

        if height[left] < height[right]:
            # left_max < right_max, update res & left
            res += left_max - height[left]
            left += 1
        else:
            # left_max >= right_max, update res & right
            res += right_max - height[right]
            right -= 1
    return res