šŸŒŠ Trapping Rain Water

šŸŸ” IntermediateTwo Pointer / Array

šŸ“‹ Problem Statement

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

Example: height = [0,1,0,2,1,0,1,3,2,1,2,1] ā†’ Output: 6 units

    ā–ˆ
    ā–ˆā–‘ā–‘ā–‘ā–ˆ
ā–ˆ...ā–ˆā–‘ā–‘ā–‘ā–ˆā–ˆā–‘ā–ˆ
ā–ˆā–ˆ.ā–ˆā–ˆ.ā–ˆā–ˆā–ˆā–ˆā–ˆā–ˆ
Water trapped = 6 units (shown as dots)

šŸ”“ Approach 1: Brute Force - O(nĀ²)

function trapBrute(array $height): int {
    $n = count($height); $total = 0;
    for ($i = 0; $i < $n; $i++) {
        $leftMax = $rightMax = 0;
        for ($j = 0; $j <= $i; $j++) $leftMax = max($leftMax, $height[$j]);
        for ($j = $i; $j < $n; $j++) $rightMax = max($rightMax, $height[$j]);
        $total += min($leftMax, $rightMax) - $height[$i];
    }
    return $total;
}

šŸŸ” Approach 2: Prefix/Suffix Max - O(n), O(n) Space

function trapPrefix(array $height): int {
    $n = count($height); if ($n < 3) return 0;

    $leftMax = array_fill(0, $n, 0);
    $rightMax = array_fill(0, $n, 0);

    $leftMax[0] = $height[0];
    for ($i = 1; $i < $n; $i++)
        $leftMax[$i] = max($leftMax[$i-1], $height[$i]);

    $rightMax[$n-1] = $height[$n-1];
    for ($i = $n-2; $i >= 0; $i--)
        $rightMax[$i] = max($rightMax[$i+1], $height[$i]);

    $total = 0;
    for ($i = 0; $i < $n; $i++)
        $total += min($leftMax[$i], $rightMax[$i]) - $height[$i];

    return $total;
}

šŸŸ¢ Approach 3: Two Pointer - O(n), O(1) Space ā­ Optimal

function trap(array $height): int {
    $n = count($height); if ($n < 3) return 0;

    $left = 0; $right = $n - 1;
    $leftMax = $height[$left];
    $rightMax = $height[$right];
    $total = 0;

    while ($left < $right) {
        if ($leftMax < $rightMax) {
            $left++;
            $leftMax = max($leftMax, $height[$left]);
            $total += $leftMax - $height[$left];
        } else {
            $right--;
            $rightMax = max($rightMax, $height[$right]);
            $total += $rightMax - $height[$right];
        }
    }
    return $total;
}

echo trap([0,1,0,2,1,0,1,3,2,1,2,1]); // 6

šŸ“ Dry Run

Step left right leftMax rightMax Water added Total
Init 0 11 0 1 - 0
1 1 11 1 1 1-1=0 0
2 2 11 1 1 1-0=1 1
3 3 11 2 1 2-2=0 1
... continuing ...
Final - - - - - 6

šŸ“Š Complexity

Brute Force O(nĀ²) O(1)
Prefix Arrays O(n) O(n)
Two Pointer O(n) O(1) ā­

šŸ’” Key Insight

Water trapped at position i = min(leftMax, rightMax) - height[i]. The two-pointer approach works because the smaller of leftMax and rightMax determines the water level at the current position.

All Problems Next: Merge Intervals