ONE HINT AWAY

18Two pointersArrays and hashing

Trapping Rain Water

Water above each bar is the lower of the tallest walls on its two sides, minus the bar.

  • 13 slides
  • Java · Python · C++ · JavaScript
  • 2 practice problems
Trapping Rain Water, slide 1 of 13
Trapping Rain Water, slide 2 of 13
Trapping Rain Water, slide 3 of 13
Trapping Rain Water, slide 4 of 13
Trapping Rain Water, slide 5 of 13
Trapping Rain Water, slide 6 of 13
Trapping Rain Water, slide 7 of 13
Trapping Rain Water, slide 8 of 13
Trapping Rain Water, slide 9 of 13
Trapping Rain Water, slide 11 of 13
Trapping Rain Water, slide 12 of 13
Trapping Rain Water, slide 13 of 13
1 / 13

The idea

Water above bar i = min(tallest wall on its left, tallest wall on its right) − height[i]. Two walkers start at the ends. Each remembers the tallest wall it has passed (leftMax, rightMax). Always settle the lower side: if height[left] < height[right], the right bar is at least as tall as every wall the left walker has passed, so the left bar holds leftMax − height[left]. Otherwise settle the right bar the same way.

Pseudocode

Pseudocode · any language
function trap(height):
    left = 0
    right = length(height) - 1
    leftMax = 0                // tallest wall seen
    rightMax = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            bar = height[left]
            leftMax = max(leftMax, bar)
            water = water + leftMax - bar
            left = left + 1
        else:
            bar = height[right]
            rightMax = max(rightMax, bar)
            water = water + rightMax - bar
            right = right - 1
    return water

The trap: moving the taller side. The rule only works when you settle the lower side: the bar on the other side is then at least as tall as every wall your walker has passed, so your own leftMax (or rightMax) decides the water. Swap the test and the example returns 5 instead of 7.

Code

public class Solution {
    public static 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]) {
                int bar = height[left];
                leftMax = Math.max(leftMax, bar);
                water = water + leftMax - bar;
                left = left + 1;
            } else {
                int bar = height[right];
                rightMax = Math.max(rightMax, bar);
                water = water + rightMax - bar;
                right = right - 1;
            }
        }
        return water;
    }
}

Complexity

  • Time: O(n). Each loop step moves one walker one place inward, so the loop runs n − 1 times.
  • Space: O(1). Five numbers (left, right, leftMax, rightMax, water) plus bar; no extra arrays.
  • Overflow: with LeetCode's limits (n ≤ 2 × 10⁴, height ≤ 10⁵) the total is below 2 × 10⁹, so a 32-bit int is enough.

How it was tested

All four versions were run from the code blocks in this file against a brute-force checker (for each bar, scan left and right for the tallest wall) on 2,016 inputs: 2,000 random arrays of length 0 to 12, plus 15 edge cases (empty, one bar, two bars, all equal, sorted, reversed, all zero, maximum heights) and one array of 20,000 bars with heights up to 100,000. All agreed. Re-run on 31 October 2026 on 3,005 more inputs (3,000 random arrays of length 0 to 12, plus the example, the quick check, the empty array, one bar and LeetCode's first example): all four matched the brute force on every one.

Practice

Try these in order. Open the worked example first if you got stuck on the slides.