Trapping Rain Water

The key idea

The water above any bar is bounded by the shorter of the tallest bar to its left and the tallest bar to its right, minus the bar itself. Two pointers let you fix that shorter wall in O(1) space.

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Each value in height is the height of a vertical bar. Rain falls and collects in the dips between taller bars. Your job is to return the total units of trapped water across the whole elevation map.

Constraints

n == height.length
1 <= n <= 2 * 10^4
0 <= height[i] <= 10^5

Examples

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

Input: height = [4,2,0,3,2,5] Output: 9

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →