Write trap(height: list[int]) -> int.
height is an elevation map of adjacent bars, each 1 unit wide. After it rains, water settles wherever it is held in by taller bars on both sides. Return the total units of water trapped.
Example: [3, 0, 2, 0, 4] gives 7: 3 units over index 1, 1 over index 2 and 3 over index 3.
[5, 1, 1, 1] gives 0, since nothing holds the water on the right.
Constraints: 0 <= len(height) <= 10^5, 0 <= height[i] <= 10^5.
Scanning left and right from every bar is O(n²) and fails the large test. Aim for O(n).
Show hint
the water above bar i depends only on the tallest bar to its left and the tallest bar to its right. Can you have both ready for every bar without rescanning?