# 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

### # 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

### # 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

### # 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19