Trapping Rain Water — Two Pointers

What does it solve?

Given bar heights, compute how much rain water is trapped between them after it rains. The water above any bar is bounded by the tallest wall to its left and right, minus the bar's own height.

Key insight: keep two pointers at the ends with running maxLeft and maxRight. Always move the pointer on the shorter side: that side's max is the true bound, so water there = max − height. No prefix arrays needed → O(N) time, O(1) space.

The core idea

// advance the shorter wall
l=0, r=n-1, ml=0, mr=0, water=0
while l < r:
  if h[l] < h[r]:
    ml=max(ml,h[l]); water+=ml-h[l]; l++
  else:
    mr=max(mr,h[r]); water+=mr-h[r]; r--

Complexity

Time complexity

O(N)

The two pointers together sweep the array once. Each bar is visited exactly once as a pointer advances inward.

Space complexity

O(1)

Only two pointers and two running maxima. No prefix/suffix arrays, unlike the O(N)-space precompute approach.

Examples & edge cases

Live animation — advance the shorter wall, bank the water

left pointer right pointer settled wall trapped water

Heights — water fills to min(maxLeft, maxRight)

Current step detail

l = — r = — maxL / maxR = — water = —

Step — of —

maxLeft

—

tallest seen left

maxRight

—

tallest seen right

water this step

—

bound − height

total water

—

accumulated

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	l	r	side moved	maxL	maxR	+ water	total

C++ implementation

trapping_rain_water.cpp

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

// Total trapped water using two pointers, O(1) space
int trap(vector<int>& h) {
    int l = 0, r = (int)h.size() - 1;
    int maxL = 0, maxR = 0, water = 0;

    while (l < r) {
        if (h[l] < h[r]) {          // left wall is shorter → its max bounds the water
            maxL = max(maxL, h[l]);
            water += maxL - h[l];
            l++;
        } else {
            maxR = max(maxR, h[r]);
            water += maxR - h[r];
            r--;
        }
    }
    return water;
}

int main() {
    vector<int> h = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << trap(h) << "\n"; // 6
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars