DATA STRUCTURES • ALGORITHMS

Trapping Rain Water

Given an elevation map represented by an array, calculating the total amount of water it can trap after a rainstorm.

Time

O(N)

Space

O(1)

Key Principle 1

Two-pointer optimization

Key Principle 2

Track leftMax and rightMax

Key Principle 3

Water at index = min(Lmax, Rmax) - height

Key Principle 4

Highly efficient O(N) space O(1)

RAIN_WATER_LAB
HEIGHTS:
Current Step
Initialize two pointers at ends. Track leftMax and rightMax.
Playback
Water Accumulator ⠿
TOTAL WATER0
LEFT MAX0
RIGHT MAX0
Trapping Logic ⠿
1int l = 0, r = n-1, leftMax = 0, rightMax = 0, total = 0;
2while (l < r) {
3    if (height[l] < height[r]) {
4        if (height[l] >= leftMax) leftMax = height[l];
5        else total += leftMax - height[l];
6        l++;
7    } else {
8        if (height[r] >= rightMax) rightMax = height[r];
9        else total += rightMax - height[r];
10        r--;
11    }
12}
L
1
2
3
4
5
6
7
8
9
10
R

Loading Lab...