← Algorithmic Patterns
hardTwo Pointers

Trapping Rain Water

Unit-width bars form an elevation profile. Calculate how many units of water remain trapped after rain.

LeetCode ↗

Work through the cases

3 examples

Input notation

Nonnegative bar heights separated by spaces.

Expected result

The total trapped water.
Case 1

Input

3 0 2 0 4

Expected output

7
Case 2

Input

1 2 3

Expected output

0
Case 3

Input

2 0 2

Expected output

2

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is, for each i, scan left and right for the tallest bars; water is \min(leftMax, rightMax) - height[i]. Correct, but O(n^2). n ≤ 2 × 10^4 can time out. The bottleneck is recomputing left/right maxima at every i. Those maxima only depend on one side and can be precomputed in linear time. Store, at each index, the highest bar to the left (inclusive) and to the right (inclusive), then sum. The water level is the shorter of the two walls — that is the DP state.

We define left[i] as the height of the highest bar to the left of and including the position at index i, and right[i] as the height of the highest bar to the right of and including the position at index i. Therefore, the amount of rainwater that can be trapped at index i is min(left[i], right[i]) - height[i]. We traverse the array to calculate left[i] and right[i], and the final answer is \sum_{i=0}^{n-1} \min(left[i], right[i]) - height[i].

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.

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];
        right[n - 1] = height[n - 1];
        for (int i = 1; i < n; ++i) {
            left[i] = Math.max(left[i - 1], height[i]);
            right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(left[i], right[i]) - height[i];
        }
        return ans;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.