Problem

In a Meta-style coding interview, you are given an array height where each element represents the height of a vertical bar in an elevation map. Return the total amount of rain water that can be trapped after raining.

Formal Specification

• Input: height, a list of non-negative integers
• Output: An integer representing the total units of trapped water

Water above index i is determined by the shorter of the tallest bar to its left and right, minus height[i], if that value is positive.

Examples

Example 1

• Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
• Output: 6
• Explanation: Water is trapped in several valleys; the total accumulated water is 6 units.

Example 2

• Input: height = [4,2,0,3,2,5]
• Output: 9
• Explanation: The bars at both ends create boundaries that trap 9 total units of water.

Constraints

• 1 <= len(height) <= 2 * 10^4
• 0 <= height[i] <= 10^5

Aim for a linear-time solution. A brute-force approach that scans left and right for every index is correct but too slow for large inputs.