View on NeetCode
View on LeetCode

Problem

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 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 array [0,1,0,2,1,0,1,3,2,1,2,1]. 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

Constraints:

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

Solution

Approach: Two Pointers

The key insight is that water at any position is determined by the minimum of the maximum heights to its left and right. We can use two pointers moving inward while tracking the maximum heights seen from both sides.

At each step, we process the side with the smaller maximum height, because that’s the limiting factor for water at that position.

Implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        water = 0

        while left < right:
            if left_max < right_max:
                # Process left side
                left += 1
                left_max = max(left_max, height[left])
                water += left_max - height[left]
            else:
                # Process right side
                right -= 1
                right_max = max(right_max, height[right])
                water += right_max - height[right]

        return water

Alternative (Dynamic Programming - Two Pass):

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        n = len(height)

        # Compute max height to the left of each position
        left_max = [0] * n
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])

        # Compute max height to the right of each position
        right_max = [0] * n
        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        # Calculate trapped water
        water = 0
        for i in range(n):
            water += min(left_max[i], right_max[i]) - height[i]

        return water

Complexity Analysis

• Time Complexity: O(n) for both approaches. The two-pointer approach makes one pass, while the DP approach makes three passes.
• Space Complexity: O(1) for two pointers, O(n) for the DP approach (storing left_max and right_max arrays).

Key Insights

1. Water Level Formula: Water at position i = min(max_left[i], max_right[i]) - height[i]. The water level is determined by the shorter of the two boundaries.

2. Two Pointers Optimization: Instead of precomputing all left_max and right_max values, we can compute them on the fly using two pointers, reducing space to O(1).

3. Process Shorter Side: We always process the side with the smaller maximum because that’s the limiting factor. If left_max < right_max, we know the water at left is limited by left_max, regardless of what’s further right.

4. No Negative Water: The formula max(0, min(left_max, right_max) - height[i]) ensures we don’t count negative water, though in practice, our max tracking ensures this naturally.

5. Edge Cases: Empty arrays or single-element arrays trap 0 water. Arrays with all decreasing or all increasing heights also trap 0 water.