Trapping Rain Water [Hard] — Two Pointers O(n)

Problem Statement

Given height array representing elevation map, compute how much water can be trapped after raining.

Input: [0,1,0,2,1,0,1,3,2,1,2,1] → Output: 6

Intuition

Two Pointer: Move from both ends. The shorter side limits water level. Track left_max and right_max. If left_max < right_max, the left pointer's water = left_max - height[left].

Solutions

C

int trap(int* height, int n) {
    int left=0, right=n-1, lmax=0, rmax=0, water=0;
    while (left<right) {
        if (height[left]<height[right]) {
            lmax=fmax(lmax,height[left]);
            water+=lmax-height[left++];
        } else {
            rmax=fmax(rmax,height[right]);
            water+=rmax-height[right--];
        }
    }
    return water;
}

C++

int trap(vector<int>& height) {
    int left=0, right=height.size()-1, lmax=0, rmax=0, water=0;
    while (left<right) {
        if (height[left]<height[right]) {
            lmax=max(lmax,height[left]);
            water+=lmax-height[left++];
        } else {
            rmax=max(rmax,height[right]);
            water+=rmax-height[right--];
        }
    }
    return water;
}

Java

public int trap(int[] height) {
    int left=0, right=height.length-1, lmax=0, rmax=0, water=0;
    while (left<right) {
        if (height[left]<height[right]) {
            lmax=Math.max(lmax,height[left]);
            water+=lmax-height[left++];
        } else {
            rmax=Math.max(rmax,height[right]);
            water+=rmax-height[right--];
        }
    }
    return water;
}

JavaScript

var trap = function(height) {
    let left=0, right=height.length-1, lmax=0, rmax=0, water=0;
    while (left<right) {
        if (height[left]<height[right]) {
            lmax=Math.max(lmax,height[left]);
            water+=lmax-height[left++];
        } else {
            rmax=Math.max(rmax,height[right]);
            water+=rmax-height[right--];
        }
    }
    return water;
};

Python

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    lmax = rmax = water = 0
    while left < right:
        if height[left] < height[right]:
            lmax = max(lmax, height[left])
            water += lmax - height[left]
            left += 1
        else:
            rmax = max(rmax, height[right])
            water += rmax - height[right]
            right -= 1
    return water

Complexity

Time: O(n)
Space: O(1)

Alternative: Monotonic Stack O(n) space

Stack stores indices of bars. When a taller bar is found, pop and compute horizontal water trapped.