hardTwo PointersPure DSA~32 min
Buffer Backpressure Capacity
A pipeline's per-stage buffer heights are given. When backpressure builds, fluid (queued items) pools in the dips between taller stages. Compute the total volume the topology can hold.
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.
Input
An array height of n integers (0 ≤ n ≤ 2·10^4), 0 ≤ height[i] ≤ 10^5.
Output
An integer — the total trapped water units.
Constraints
- Water above index i is bounded by min(maxLeft, maxRight) − height[i]
- 0 ≤ n ≤ 20,000
- Target O(n) time, O(1) extra space
Examples
Example 1
Input
[0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
Water pools in the valleys between the peaks for 6 total units.
Example 2
Input
[4,2,0,3,2,5]
Output
9
The dip between the 4 and 5 walls traps 9 units.