Trapping Rain water problem

Hard

Problem

height[i] is the height of a bar of width 1. After it rains, water collects between taller bars. Return the total units of water trapped.

Example 1

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

Water above each bar = min(tallest bar to its left, tallest to its right) − its own height, if positive.

Test cases

Case 1

Input:    [0,1,0,2,1,0,1,3,2,1,2,1]
Expected: 6

Case 2

Input:    [4,2,0,3,2,5]
Expected: 9

Case 3

Input:    [2,0,2]
Expected: 2

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution3 approaches

1. Prefix max arrays

Time O(n)Space O(n)

Water above bar i = min(maxLeft[i], maxRight[i]) − height[i]. Precompute both in two passes.

function trap(h) {
const n = h.length;
const left = Array(n), right = Array(n);
left[0] = h[0];
for (let i = 1; i < n; i++) left[i] = Math.max(left[i - 1], h[i]);
right[n - 1] = h[n - 1];
for (let i = n - 2; i >= 0; i--) right[i] = Math.max(right[i + 1], h[i]);
let water = 0;
for (let i = 0; i < n; i++) water += Math.min(left[i], right[i]) - h[i];
return water;
}

2. Two pointers

Time O(n)Space O(1)

Move the side with the smaller running max inward; that side bounds the water. Drops space to O(1).

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

3. Monotonic stack

Time O(n)Space O(n)

Keep a decreasing stack of indices; when a taller bar arrives, pop and add the water trapped in the "valley".

function trap(h) {
const st = [];
let water = 0;
for (let i = 0; i < h.length; i++) {
while (st.length && h[i] > h[st[st.length - 1]]) {
const bottom = st.pop();
if (!st.length) break;
const width = i - st[st.length - 1] - 1;
const bounded = Math.min(h[i], h[st[st.length - 1]]) - h[bottom];
water += width * bounded;
}
st.push(i);
}
return water;
}