Table of Contents
Open Table of Contents
Problem
Given n
nonnegative integers representing an elevation map where the width of each bar is 1, the task is to compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: 6 units of rainwater are trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
Explanation: 9 units of rainwater are trapped.
Constraints:
n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5
Explanation/Approach
This problem asks for the total amount of rainwater that can be trapped within the given elevation map. There are several ways to approach this problem:
TwoPointer Approach:
 Left and Right Pointers: Initialize two pointers, one at the start and one at the end of the array.
 Iterative Trapping: Move the pointers towards each other, calculating and updating the amount of trapped water at each step.
Dynamic Programming Approach:
 Precompute Maximum Heights: Compute the maximum height to the left and right of every bar.
 Calculate Trapped Water: Iterate through each bar and calculate the trapped water based on the minimum of the max heights on either side minus the height of the current bar.
Using a Stack:
 Stack for Bars: Use a stack to keep track of bars.
 Calculate Trapped Water: When the current bar is taller than the bar at the top of the stack, calculate the trapped water between them.
Solution: TwoPointer Approach
class Solution:
def trap(self, height: List[int]) > int:
# Check if the height array is empty. If yes, return 0 as no water can be trapped.
if not height:
return 0
# Initialize two pointers for scanning the height array from both ends.
left, right = 0, len(height)  1
# Initialize left_max and right_max to keep track of the maximum height seen so far
# from the left and right sides, respectively.
left_max, right_max = height[left], height[right]
# Initialize a variable to accumulate the total amount of trapped water.
trapped_water = 0
# Loop through the height array until the left and right pointers meet.
while left < right:
# If the maximum height on the left is less than the maximum on the right,
# process the left side.
if left_max < right_max:
left += 1 # Move the left pointer to the right.
left_max = max(left_max, height[left]) # Update the left_max if necessary.
trapped_water += left_max  height[left] # Add trapped water above the current bar.
# Otherwise, process the right side.
else:
right = 1 # Move the right pointer to the left.
right_max = max(right_max, height[right]) # Update the right_max if necessary.
trapped_water += right_max  height[right] # Add trapped water above the current bar.
# Return the total amount of trapped water.
return trapped_water
Time and Memory Complexity
The time complexity is O(n), where n is the number of elements in height
, as we pass through the array only once. The space complexity is O(1), as we only use constant extra space.
Explanation
Initialization:
left = 0, right = len(height)  1 left_max = height[left], right_max = height[right] trapped_water = 0 Iteration:
While left < right: If left_max <= right_max, move left pointer to the right. Else, move right pointer to the left. Calculating Trapped Water:
Update left_max and right_max. Add min(left_max, right_max)  height[current] to trapped_water.
Visual Representation
Initial Configuration:
Elevation Map: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Left Pointer (L): At index 0
Right Pointer (R): At index 11
left_max = 0, right_max = 1
Trapped Water = 0
Iteration Steps:

Step 1:
L v [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] ^ R left_max = 0, right_max = 1 Trapped Water = 0 (No trapping as left_max < height[L])

Step 2:
L v [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] ^ R left_max = 1, right_max = 1 Trapped Water = 0 + 0 = 0

Continuing the Process:
Moving L and R towards each other, updating left_max and right_max. Calculating trapped water at each step.
Solution: Dynamic Programming Approach
class Solution:
def trap(self, height: List[int]) > int:
# If height list is empty, return 0 as no water can be trapped.
if not height:
return 0
n = len(height)
# Initialize two lists to store the maximum height of bars to the left and right of each bar.
left_max = [0] * n
right_max = [0] * n
# Fill the left_max list. For each bar, store the maximum height observed so far from the left.
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i1], height[i])
# Fill the right_max list. For each bar, store the maximum height observed so far from the right.
right_max[n1] = height[n1]
for i in range(n2, 1, 1):
right_max[i] = max(right_max[i+1], height[i])
# Calculate the trapped water for each bar.
trapped_water = 0
for i in range(n):
# The water trapped on top of the current bar is the minimum of the maximum heights
# to its left and right, minus the height of the bar itself.
trapped_water += min(left_max[i], right_max[i])  height[i]
# Return the total amount of trapped water.
return trapped_water
Time and Memory Complexity
The time complexity is O(n), and the space complexity is O(n) for storing the left_max
and right_max
arrays.
Explanation
This approach precomputes the maximum height to the left and right of every element. The trapped water at each position is the minimum of these two heights minus the height of the bar itself.
Initial Configuration:
Elevation Map: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
left_max: [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]
right_max: [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]
Calculation of Trapped Water:
 For each index
i
, calculatemin(left_max[i], right_max[i])  height[i]
.  Sum these values for the total trapped water.
Solution: Using a Stack
class Solution:
def trap(self, height: List[int]) > int:
# Initialize an empty stack and a variable for trapped water.
stack = []
trapped_water = 0
# Iterate through each bar in the height array.
for i, h in enumerate(height):
# If there's a bar that can trap water (i.e., a bar taller than the last one on the stack),
# we calculate the trapped water.
while stack and height[stack[1]] < h:
# Pop the top element from the stack.
top = stack.pop()
# If the stack is empty after popping, break out of the loop.
if not stack:
break
# Calculate the distance between the current bar and the bar at the new top of the stack.
distance = i  stack[1]  1
# Calculate the bounded height which is the min height of two sides minus the height of the top bar.
bounded_height = min(height[stack[1]], h)  height[top]
# Add the trapped water for this portion.
trapped_water += distance * bounded_height
# Append the current index to the stack.
stack.append(i)
# Return the total amount of trapped water.
return trapped_water
Time and Memory Complexity
The time complexity is O(n), and the space complexity is O(n) for the stack.
Explanation
The stack is used to keep track of the bars. When we find a bar that is taller than the one on top of the stack, we calculate the trapped water between them.
Visual Representation
Initial Configuration:
Elevation Map: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Stack: []
Trapped Water = 0
Iteration Steps:

Pushing bars onto the stack:
For each bar, if it is not higher than the bar at the top of the stack, push its index onto the stack.

Calculating Trapped Water:
When encountering a taller bar:  Pop the stack and calculate the water trapped with the current bar.  Calculate the distance and bounded height.  Add to Trapped Water.