Trapping Rain Water

HardTwo PointersNeetCode 150SeniorOpen on LeetCodeUpdated Sep 21, 2026

You're given an array height of non-negative integers that describes an elevation map. Each bar has width 1, and height[i] is the height of the bar at position i, with the bars standing side by side. After it rains, water collects in the dips between bars. Return the total number of units of water trapped. Water runs off past the first and last bars, so nothing is held beyond the two ends.

Examples

height = [0,1,0,2,1,0,1,3,2,1,2,1] returns 6

The water resting between the bars adds up to 6 units.

Index 2 holds 1 unit between the bars of height 1 and 2. Indices 4, 5 and 6 fill up to level 2, holding 1, 2 and 1 units, and index 9 holds 1 unit. That's 1 + 4 + 1 = 6.

height = [4,2,0,3,2,5] returns 9

Everything between the bar of height 4 and the bar of height 5 fills to level 4, the shorter of the two. That puts 2 + 4 + 1 + 2 = 9 units above indices 1 to 4.

Constraints

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

Hints

Hint 1

Focus on one position. How high can water stand above it, and what on its left and right decides that?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Water above index i is min(tallest bar on its left, tallest bar on its right) minus height[i]. Walk l and r inward from the ends, tracking leftMax and rightMax. If leftMax < rightMax, the right side is already known to have a bar at least that tall, so leftMax is the true level for the next left index: step l, update leftMax, add leftMax - height[l]. Otherwise do the mirror step on the right.

Time

O(n)

Space

O(1)

Pitfall

Always advance the side whose running max is smaller, since only that max is a proven water level. Advancing the other side can overcount. Update the max before adding water, so a new tallest bar adds 0 instead of a negative amount.

Solutions

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1;
        int leftMax = height[l], rightMax = height[r];
        int water = 0;
        while (l < r) {
            if (leftMax < rightMax) {
                l++;
                leftMax = Math.max(leftMax, height[l]);
                water += leftMax - height[l];
            } else {
                r--;
                rightMax = Math.max(rightMax, height[r]);
                water += rightMax - height[r];
            }
        }
        return water;
    }
}

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        left_max, right_max = height[l], height[r]
        water = 0
        while l < r:
            if left_max < right_max:
                l += 1
                left_max = max(left_max, height[l])
                water += left_max - height[l]
            else:
                r -= 1
                right_max = max(right_max, height[r])
                water += right_max - height[r]
        return water