Problem
Bars of width 1 have the given heights. After rain, water collects above each bar up to the lower of the tallest bars on its left and right. Compute the total trapped water. An O(n) two-pointer solution is expected.
Implement trapped_water(heights).
Input
heights: Bar heights from left to right.
Output
Return the total units of water.
Constraints
0 ≤ length ≤ 200,000; 0 ≤ height ≤ 100,000
Examples
Input:
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Expected output:
expected = 6Input:
std::vector<long long> heights = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Expected output:
long long expected = 6;Input:
long[] heights = new long[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
Expected output:
long expected = 6;Explanation
Water fills the dips: 1 + 1 + 2 + 1 + 1 = 6 units.
Input:
heights = [3, 2, 1]
Expected output:
expected = 0Input:
std::vector<long long> heights = {3, 2, 1};
Expected output:
long long expected = 0;Input:
long[] heights = new long[] {3, 2, 1};
Expected output:
long expected = 0;Explanation
Heights only go down, so water runs off: 0.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Each position’s water level is limited by the shorter tallest bar seen on its left and right.
Hint 2
Track boundaries from both ends, always advancing the side with the smaller current boundary.
Hint 3
Be careful with empty input and equal-height plateaus; only the smaller side can determine trapped water there.
Expected complexity
O(n) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.