Trapping Rain Water

Hard Problem 21 of 151 Java and Python

Practice on LeetCode

Problem

You are given n non-negative integers height describing an elevation map where every bar is 1 unit wide.

Return how many units of 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 ≤ n ≤ 2 × 10⁴
0 ≤ height[i] ≤ 10⁵

Explanation

The water above bar i is min(tallest bar to its left, tallest bar to its right) - height[i] (never below 0). Work this out per bar and add it up.

Precomputing both maximums takes two extra arrays. Two pointers remove them: whichever side has the smaller maximum so far is the limiting wall, so that side's water is already known.

Approach 1 · Naive

Scan left and right for every bar

Time O(n²)
Space O(1)

For each bar, find the tallest bar on each side by scanning, and add the trapped water.

For each i, scan left for maxLeft and right for maxRight (both including i).
Add min(maxLeft, maxRight) - height[i].

Java

class Solution {
    public int trap(int[] height) {
        int water = 0;
        for (int i = 0; i < height.length; i++) {
            int maxLeft = 0;
            int maxRight = 0;
            for (int j = i; j >= 0; j--) {
                maxLeft = Math.max(maxLeft, height[j]);
            }
            for (int j = i; j < height.length; j++) {
                maxRight = Math.max(maxRight, height[j]);
            }
            water += Math.min(maxLeft, maxRight) - height[i];
        }
        return water;
    }
}

Python

class Solution:
    def trap(self, height: List[int]) -> int:
        water = 0
        for i in range(len(height)):
            max_left = max(height[:i + 1])
            max_right = max(height[i:])
            water += min(max_left, max_right) - height[i]
        return water

Approach 2 · Better

Prefix and suffix maximums

Time O(n)
Space O(n)

Precompute the tallest bar up to each index from the left, and from the right. Then each bar's water is one lookup.

left[i] = max(left[i - 1], height[i]).
right[i] = max(right[i + 1], height[i]).
Sum min(left[i], right[i]) - height[i].

Java

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = height[0];
        for (int i = 1; i < n; i++) {
            left[i] = Math.max(left[i - 1], height[i]);
        }
        right[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i]);
        }
        int water = 0;
        for (int i = 0; i < n; i++) {
            water += Math.min(left[i], right[i]) - height[i];
        }
        return water;
    }
}

Python

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left, right = [0] * n, [0] * n
        left[0] = height[0]
        for i in range(1, n):
            left[i] = max(left[i - 1], height[i])
        right[-1] = height[-1]
        for i in range(n - 2, -1, -1):
            right[i] = max(right[i + 1], height[i])
        return sum(min(left[i], right[i]) - height[i] for i in range(n))

Approach 3 · Optimal

Two pointers

Time O(n)
Space O(1)

Move inwards from both ends, keeping the highest bar seen on each side. Process the side whose maximum is smaller: its water level is decided by that maximum.

Set left = 0, right = n - 1, leftMax = rightMax = 0.
If height[left] < height[right]: update leftMax, add leftMax - height[left], move left.
Otherwise: update rightMax, add rightMax - height[right], move right.

Java

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

Python

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

Complexity compared

Approach	Time	Space
Naive Scan left and right for every bar	O(n²)	O(1)
Better Prefix and suffix maximums	O(n)	O(n)
Optimal Two pointers	O(n)	O(1)

Key takeaways

Start from the per-element formula, then optimise how you get its inputs: scan, precompute, then two pointers.
A monotonic stack is another O(n) solution that fills water layer by layer.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem