Trapping Rain Water
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

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
- Are all bars width 1 and heights non-negative? (Here: yes.)
- Does water spill off both ends? (Here: yes, the ends have no wall.)
- Is the input one-dimensional? The 2D version needs a heap; good to know if it's the follow-up.
- 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.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.