Trapping Rain Water

HardTwo Pointers

Given an elevation map of bar heights, compute how much rain water it can trap between the bars.

Constraints

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

Two pointers with running maxima

Time O(n)Space O(1)

Water above each bar is limited by the smaller of the tallest bars to its left and right. Move two pointers inward, always advancing the side with the smaller running maximum and adding its trapped water.

#include <bits/stdc++.h>
using namespace std;

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