Total Rainwater Trapped Above an Elevation Profile of Unit-Width Bars

An elevation profile is made of vertical bars of width 1 standing side by side on flat ground. After heavy rain, water collects in the dips between bars, and any water that is not held in place by taller bars on both sides runs off the ends of the profile.

Given the bar heights from left to right, return the total amount of water that stays trapped, measured in unit squares.

Function Signature

def trapped_water(heights: list[int]) -> int:

heights[i] is the height of the bar at position i, from left to right.

Rules

• Bar i has width 1 and height heights[i]. Bars stand next to each other with no gaps, and a height of 0 means bare ground at that position.
• A unit square of water at position i and level y (the band between heights y and y + 1) stays trapped exactly when heights[i] <= y, some bar strictly taller than y stands to the left of i, and some bar strictly taller than y stands to the right of i. All other water runs off; there are no walls beyond the first and last bars.
• Return the total number of trapped unit squares.

Constraints

• 1 <= len(heights) <= 10^5
• 0 <= heights[i] <= 10^5
• The answer can exceed 2^31 - 1 (it is below 10^10). Python integers handle this.

Examples

Example 1

Input: heights = [3, 0, 2, 0, 4]
Output: 7

The water between the bar of height 3 and the bar of height 4 settles at level 3. Positions 1, 2 and 3 hold 3, 1 and 3 units.

Example 2

Input: heights = [1, 2, 3, 2, 1]
Output: 0

No position has a taller bar on both sides, so all water runs off.

Example 3

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

Position 1 holds 2 units between the two bars of height 2. Positions 3, 4 and 5 fill to level 2, between the bar of height 2 at position 2 and the bar of height 3 at position 6, holding 1, 2 and 1 units.