HardLeetCode #42Two Pointers

Trapping Rain Water

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.

Constraints

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

Examples

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

Output: 6

Solution

Approach

Use two pointers. Track max height from left and right. Water at each position = min(leftMax, rightMax) - height[i]. Move pointer with smaller max inward.

def trap(height):
    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:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]
    return water

Complexity

Time:O(n)

Space:O(1)

Hints

1.Water at position i depends on max heights on both sides
2.Can you avoid computing max arrays?
3.Two pointers with running max from each side

Asked at

Google