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.

Additional information

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

Example 1:

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

Output: 6

Explanation: The above elevation map (black section) is represented by the array. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4, 2, 0, 3, 2, 5]

Output: 9

Brute Force (Time Limit Exceeded)

Intuition
For any specific bar at index i, the amount of water it can hold is determined by the highest bars to its left and right. specifically, min(max_left, max_right) - height[i]. We can iterate through every element and scan left/right every time to find these maximums.

Algorithm

1. Initialize total_water to 0.
2. Iterate through the array from index 1 to n-2.
3. For each element i:

• Scan left to find max_left.
• Scan right to find max_right.
• Calculate water = min(max_left, max_right) - height[i].
• If water > 0, add it to total_water.

def trap(height: list[int]) -> int:
    n = len(height)
    res = 0
    
    for i in range(1, n - 1):
        left_max = height[i]
        for j in range(i):
            left_max = max(left_max, height[j])
        
        right_max = height[i]
        for j in range(i + 1, n):
            right_max = max(right_max, height[j])
            
        res += min(left_max, right_max) - height[i]
        
    return res

Time & Space Complexity

• Time complexity: O(n^2)
• Space complexity: O(1)

Prefix & Suffix Max Arrays (Dynamic Programming)

Intuition
In the brute force approach, we repeatedly scan for the left and right maximums. We can optimize this by pre-computing these values. We can create a left_max array where left_max[i] stores the maximum height from index 0 to i, and similarly a right_max array for the right side. This allows us to query the maximums in O(1) time.

Algorithm

1. Create two arrays, left_max and right_max, of size n.
2. Fill left_max: iterate from left to right, storing the running maximum height.
3. Fill right_max: iterate from right to left, storing the running maximum height.
4. Iterate through the array and calculate min(left_max[i], right_max[i]) - height[i] to find the trapped water at each index.

def trap(height: list[int]) -> int:
    if not height:
        return 0
    
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n
    
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(height[i], left_max[i - 1])
        
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(height[i], right_max[i + 1])
        
    res = 0
    for i in range(n):
        res += min(left_max[i], right_max[i]) - height[i]
        
    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: We iterate through the array three times (left pass, right pass, calculation pass).

• Space complexity: O(n)

• Reason: We use two extra arrays of size n to store the prefix and suffix maximums.

Two Pointers (Optimal)

Intuition
We can optimize the space further. Notice that we only need the minimum of (max_left, max_right). If we use two pointers, one at the left (l) and one at the right (r), we can decide which side to process based on which height is smaller. If left_max < right_max, the water level at l is definitely limited by left_max, regardless of what happens between l and r.

Algorithm

1. Initialize l = 0, r = n - 1.
2. Initialize left_max and right_max to the heights at the ends.
3. Initialize res = 0.
4. While l < r:

• If left_max < right_max:

• Increment l.

• Update left_max.

• Add left_max - height[l] to res.

• Else:

• Decrement r.

• Update right_max.

• Add right_max - height[r] to res.

def trap(height: list[int]) -> int:
    if not height:
        return 0
    
    l, r = 0, len(height) - 1
    left_max, right_max = height[l], height[r]
    res = 0
    
    while l < r:
        if left_max < right_max:
            l += 1
            left_max = max(left_max, height[l])
            res += left_max - height[l]
        else:
            r -= 1
            right_max = max(right_max, height[r])
            res += right_max - height[r]
            
    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: Single pass with two pointers.

• Space complexity: O(1)

• Reason: Constant extra space.