Trapping Rain Water [Hard] — Two Pointer Classic

Problem Statement

Given heights of bars, compute how much water can be trapped.

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

Intuition

Water at position i = min(left_max[i], right_max[i]) - height[i].

Two Pointer: Track running lmax and rmax. Smaller side limits water. Move from the smaller side inward.

Solutions

C

int trap(int* h, int n){
    int l=0,r=n-1,lm=0,rm=0,w=0;
    while(l<r){if(h[l]<h[r]){lm=fmax(lm,h[l]);w+=lm-h[l++];}else{rm=fmax(rm,h[r]);w+=rm-h[r--];}}
    return w;
}

C++

int trap(vector<int>& height) {
    int l=0,r=height.size()-1,lm=0,rm=0,w=0;
    while(l<r){
        if(height[l]<height[r]){lm=max(lm,height[l]);w+=lm-height[l++];}
        else{rm=max(rm,height[r]);w+=rm-height[r--];}
    }
    return w;
}

Java

public int trap(int[] h) {
    int l=0,r=h.length-1,lm=0,rm=0,w=0;
    while(l<r){
        if(h[l]<h[r]){lm=Math.max(lm,h[l]);w+=lm-h[l++];}
        else{rm=Math.max(rm,h[r]);w+=rm-h[r--];}
    }
    return w;
}

JavaScript

var trap = function(height) {
    let l=0,r=height.length-1,lm=0,rm=0,w=0;
    while(l<r){
        if(height[l]<height[r]){lm=Math.max(lm,height[l]);w+=lm-height[l++];}
        else{rm=Math.max(rm,height[r]);w+=rm-height[r--];}
    }
    return w;
};

Python

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

Complexity

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