deepSWE.io

Trapping Rain Water

ArraysTwo PointersDynamic Programming

Problem Statement

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example

Heights:

Water:

Total Water Trapped: 6 units

Water is trapped between the elevation bars

Trapped Water

Ground/Bars

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation:

The elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]
In this case, 6 units of rain water are trapped
Water is trapped between the bars based on the height differences

Constraints

• n == height.length
• 1 ≤ n ≤ 2 × 10⁴
• 0 ≤ height[i] ≤ 3 × 10⁴

Solution Approaches

• Brute Force: For each element, find max height on left and right (O(n²))
• Dynamic Programming: Precompute max heights for each position (O(n))
• Two Pointers: Use two pointers to track max heights (O(n), O(1) space)
• Stack: Use monotonic stack to track trapped water (O(n))

Algorithm Explanation

The Trapping Rain Water problem can be solved efficiently using the two-pointer approach. The key insight is that water level at any position depends on the minimum of the maximum heights to its left and right.

Key Steps (Two Pointers)

Initialize: Set left and right pointers at array ends, track max heights on both sides.
Move Pointers: Move the pointer with smaller max height inward.
Calculate Water: Water trapped = min(left_max, right_max) - current_height.
Update Max: Update the maximum height for the side we're processing.

Solution Properties

Time Complexity: O(n) - single pass through array
Space Complexity: O(1) - only using constant extra space
Optimal: Uses two pointers to avoid extra space for precomputation
Intuitive: Water level depends on the bottleneck (minimum of left/right max)

Trapping Rain Water Visualization

Two Pointers Approach

Left Pointer

Index: 0 | Max: 0

Right Pointer

Index: 11 | Max: 0

Start: Initialize two pointers

Start with pointers at both ends of the array

Total Water Trapped: 0 units

Step 1 of 24

Trapped Water

Ground/Bars

Left Pointer

Right Pointer

Code Example

def trap(height: List[int]) -> int:
    """
    Calculate the amount of rainwater that can be trapped.
    
    Args:
        height: List of non-negative integers representing elevation map
        
    Returns:
        Integer representing total units of trapped rainwater
        
    Time complexity: O(n) - single pass through array
    Space complexity: O(1) - only using constant extra space
    """
    if not height or len(height) < 3:
        return 0
    
    # Initialize two pointers at the ends
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    trapped_water = 0
    
    # Process until pointers meet
    while left < right:
        # Process the side with smaller height
        if height[left] < height[right]:
            # If current height is greater than left_max, update it
            if height[left] >= left_max:
                left_max = height[left]
            else:
                # Water can be trapped: left_max - current_height
                trapped_water += left_max - height[left]
            left += 1
        else:
            # If current height is greater than right_max, update it
            if height[right] >= right_max:
                right_max = height[right]
            else:
                # Water can be trapped: right_max - current_height
                trapped_water += right_max - height[right]
            right -= 1
    
    return trapped_water