Trapping Rain water problem
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
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;}