Trapping Rain Water

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    You are given the heights of bars of width 1 standing side by side. After it rains, how many units of water are trapped between them? Water above a bar can rise only as high as the shorter of the tallest bars to its left and right; water at the ends runs off.

    This is the classic "hard" problem that becomes short once you see the right formula. Interviewers like it because there's a clear ladder: brute force, precomputed arrays, then two pointers with O(1) space. Original problem: LeetCode 42.

    Example

    Grey bars of heights 0,1,0,2,1,0,1,3,2,1,2,1 hold six units of water in their dips.
    Grey bars of heights 0,1,0,2,1,0,1,3,2,1,2,1 hold six units of water in their dips.
    Input:  [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    Output: 6
    Input:  [4, 2, 0, 3, 2, 5]
    Output: 9

    Constraints (assumed)

    • 1 ≤ n ≤ 2 × 10⁴.
    • 0 ≤ height[i] ≤ 10⁵.

    What this question tests

    • Finding the per-position formula instead of simulating water.
    • Improving from O(n²) to O(n) time with precomputation, then to O(1) space with two pointers.
    • Explaining why the two-pointer move is safe.

    Questions to ask first

    1. Are all bars width 1 and heights non-negative? (Here: yes.)
    2. Does water spill off both ends? (Here: yes, the ends have no wall.)
    3. Is the input one-dimensional? The 2D version needs a heap; good to know if it's the follow-up.
    4. How big can the total be? Up to n × max height ≈ 2 × 10⁹, which can overflow 32-bit ints; use 64-bit if limits grow.