[/dsa/leetcode]

42 - Trapping Rain Water

Wednesday, 16 September 2026

<hard> [problem]

Water above a bar is capped by the shorter of the tallest bars on either side, first with one prefix max array, then with two pointers in O(1) space.

{array}{two pointers}{prefix sum}

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

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

Approach

The water in a level i is calculated by min(leftwall, rightwall) - height of curr wall

water[i] = min(maxLeft[i], maxRight[i]) - height[i]

Due to this maxLeft and maxRight, its gets converted to a prefix and suffix sum problem.

The maxima are just a running max from each end, so precompute them. The usual version keeps two arrays, but one is enough: fill it left to right, then consume it right to left while a single variable carries the right max. Once left[i] has been read it’s dead, so nothing is lost. See the prefix and suffix arrays note.

class Solution {
public:
    int trap(vector<int>& height) {
        const int n = height.size();
        vector<int> left(n);
        int maxi = 0;
        for (int i = 0; i < n; i++) {
            left[i] = maxi;
            maxi = max(maxi, height[i]);
        }

        int res = 0;
        maxi = 0;
        for (int i = n - 1; i >= 0; i--) {
            int level = min(maxi, left[i]);
            if (level > height[i]) res += level - height[i];
            maxi = max(maxi, height[i]);
        }
        return res;
    }
};

Assigning before updating maxi makes both maxima exclusive — they skip height[i] itself — which is one off from the formula above. It still comes out right, but only because of the level > height[i] guard: when bar i is the tallest on one side, its exclusive max is shorter than the bar, so the subtraction goes negative exactly where the inclusive version would give 0. The clamp maps one to the other.

height = [4, 2, 0, 3, 2, 5]
left    = [0, 4, 4, 4, 4, 4]      exclusive max from the left
i=5  level=min(0,4)=0  h=5  ->  0
i=4  level=min(5,4)=4  h=2  ->  +2
i=3  level=min(5,4)=4  h=3  ->  +1
i=2  level=min(5,4)=4  h=0  ->  +4
i=1  level=min(5,4)=4  h=2  ->  +2
i=0  level=min(5,0)=0  h=4  ->  0      total 9
  • time: O(n) — two passes
  • space: O(n) — the one array

Two Pointers

You never need both maxima, only the smaller one, so there’s no reason to compute the larger. Walk l and r inward from the ends, always advancing whichever side has the shorter bar.

When height[l] < height[r], the bar at r is itself taller than height[l], so whatever the true right max turns out to be, it’s at least that tall and cannot be the binding wall for l. lMax is the constraint, and the water at l can be settled immediately without ever knowing the right side. The mirror argument covers the other branch.

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int lMax = 0, rMax = 0, res = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                lMax = max(lMax, height[l]);
                res += lMax - height[l];
                l++;
            } else {
                rMax = max(rMax, height[r]);
                res += rMax - height[r];
                r--;
            }
        }
        return res;
    }
};
height = [4, 2, 0, 3, 2, 5]
l=0 r=5  4 < 5  lMax=4  +0   res=0
l=1 r=5  2 < 5  lMax=4  +2   res=2
l=2 r=5  0 < 5  lMax=4  +4   res=6
l=3 r=5  3 < 5  lMax=4  +1   res=7
l=4 r=5  2 < 5  lMax=4  +2   res=9
l=5 r=5  stop                res=9
  • time: O(n) — every step moves a pointer inward
  • space: O(1) — four ints
quantinium © 2026