ProblemHardLeetCode #428 min read

Trapping Rain Water

How much water can a 1D elevation map hold? Two-pointer solution in O(n) without prefix arrays.

arraystwo-pointersmonotonic

Intro

Given non-negative bar heights of width 1, compute how much water can be trapped after raining. The classic O(n) solution stores left-max and right-max; the two-pointer trick avoids the O(n) extra space.

Key insight

Water at index i depends only on the smaller of (max to the left, max to the right). Walk from both ends and process whichever side currently has the smaller max — that side's water is fully determined.

Approach

1left = 0, right = n - 1, leftMax = rightMax = 0.
2If h[left] < h[right]: if h[left] >= leftMax, update leftMax; else add leftMax - h[left]; left++.
3Else: symmetric on the right side.

Complexity

Time

O(n)

Space

O(1)

Code

Snippetjava

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

Pitfalls

Forgetting that the two-pointer correctness rests on the smaller-side argument.
Stack-based solution can be more intuitive but harder to write under pressure.

Variants & follow-ups

Trapping Rain Water II (LC 407) — heap-based