Problem statement

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.

Example 1

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

Example 2

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

Constraints

• 1 <= height.length <= 30
• 0 <= height[i] <= 100

Hints for Trapping Rain Water

1. Hint 1

   Water above position i is min(maxLeft, maxRight) - height[i].

2. Hint 2

   Two pointers moving inward, tracking the running max from each side, gives O(n)/O(1).

How to solve Trapping Rain Water

Water above a bar is limited by the shorter of the tallest wall to its left and the tallest to its right. Two pointers let you resolve that without precomputing both arrays: whichever side is currently shorter is the binding constraint, so that side can be settled and advanced immediately.

Approach

1. Put l at the start and r at the end, tracking leftMax and rightMax.
2. If height[l] < height[r], the left side is the limiting one.
3. In that case: if height[l] is at least leftMax, it becomes the new leftMax; otherwise it traps leftMax - height[l]. Advance l.
4. Otherwise do the mirror image on the right and move r inward.
5. Continue until the pointers meet.

Why it works

When height[l] < height[r], there is guaranteed to be some wall on the right at least as tall as height[r], so the water above position l is decided entirely by leftMax — the right side cannot be the smaller of the two. That makes the left position safe to finalise without knowing the actual right maximum, which is what removes the need for a precomputed suffix array. The mirror argument covers the other branch, and each step retires one position.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Advance the pointer on the shorter side; moving the taller one breaks the guarantee the argument depends on.
• Update the running maximum or add water, never both for the same bar.
• Water is max - height, which is 0 at a new maximum — no negative contributions.
• Compare height[l] with height[r], not leftMax with rightMax, when deciding which side to move.

Reference solution

Python

from typing import List

def trap(height: List[int]) -> int:
    l, r = 0, len(height) - 1
    lm = rm = water = 0
    while l < r:
        if height[l] < height[r]:
            lm = max(lm, height[l])
            water += lm - height[l]
            l += 1
        else:
            rm = max(rm, height[r])
            water += rm - height[r]
            r -= 1
    return water

Java

public static int trap(int[] height) {
    int l = 0, r = height.length - 1, leftMax = 0, rightMax = 0, total = 0;
    while (l < r) {
        if (height[l] < height[r]) {
            if (height[l] >= leftMax) leftMax = height[l];
            else total += leftMax - height[l];
            l++;
        } else {
            if (height[r] >= rightMax) rightMax = height[r];
            else total += rightMax - height[r];
            r--;
        }
    }
    return total;
}

C++

int trap(vector<int>& height) {
    int l = 0, r = (int) height.size() - 1, leftMax = 0, rightMax = 0, total = 0;
    while (l < r) {
        if (height[l] < height[r]) {
            if (height[l] >= leftMax) leftMax = height[l];
            else total += leftMax - height[l];
            l++;
        } else {
            if (height[r] >= rightMax) rightMax = height[r];
            else total += rightMax - height[r];
            r--;
        }
    }
    return total;
}

JavaScript

var trap = function(height) {
    let l = 0, r = height.length - 1;
    let lm = 0, rm = 0, water = 0;
    while (l < r) {
        if (height[l] < height[r]) {
            lm = Math.max(lm, height[l]);
            water += lm - height[l];
            l++;
        } else {
            rm = Math.max(rm, height[r]);
            water += rm - height[r];
            r--;
        }
    }
    return water;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard