Trapping Rainwater — Two Pointer Approach

What does it solve?

Given an array of non-negative integers representing bar heights, find the total amount of rainwater that can be trapped between the bars after it rains.

Water above a bar at index i = min(maxLeft, maxRight) − height[i]. We use two pointers to compute this in one pass.

Two-pointer logic

// Move the smaller side inward
if (leftMax < rightMax):
  water += leftMax − height[L]
  L++
else:
  water += rightMax − height[R]
  R--

Complexity

Time complexity

O(n)

Two pointers sweep inward — each index visited exactly once.

Space complexity

O(1)

Only four variables: L, R, leftMax, rightMax. No extra arrays.

Examples & edge cases

Live animation

Left pointer (L) Right pointer (R) Trapped water leftMax / rightMax walls

Total water

—

units

Left pointer

—

leftMax —

Right pointer

—

rightMax —

Step

—

Select an example and press Play to begin.

✓ Complete

Speed Medium

Step-by-step table

Step	L	R	leftMax	rightMax	Action	Water added	Total water

C++ implementation

trapping_rainwater.cpp

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

int trap(vector<int>& height) {
    int L = 0, R = height.size() - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;

    while (L < R) {
        if (height[L] < height[R]) {
            // Left side is the bottleneck
            if (height[L] >= leftMax)
                leftMax = height[L];       // update left max wall
            else
                water += leftMax - height[L]; // trap water here
            L++;
        } else {
            // Right side is the bottleneck
            if (height[R] >= rightMax)
                rightMax = height[R];      // update right max wall
            else
                water += rightMax - height[R]; // trap water here
            R--;
        }
    }
    return water;
}

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

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars