Given an elevation map, compute how much water it can trap after raining.

Interview question: Trapping Rain Water

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.

## Example
```
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
```

## Constraints
* `n == height.length`
* `1 <= n <= 2 * 10^4`
* `0 <= height[i] <= 10^5`

- Water above an index is limited by the tallest wall on its left and the tallest wall on its right.
- If the shorter of those two walls is taller than the current bar, the difference is trapped water.
- Bars at the ends cannot trap water because one side is open.

Understand What Water Needs

- A direct dynamic programming solution precomputes `left_max[i]` and `right_max[i]`.
- Then each index contributes `min(left_max[i], right_max[i]) - height[i]` if that value is positive.
- This is correct but uses O(n) extra space.

Start with Prefix and Suffix Maximums

- We can avoid the extra arrays by scanning from both ends.
- Whichever side has the smaller current maximum is the limiting side for that step.
- If `left_max <= right_max`, the left position's water is already determined; otherwise the right position's water is determined.

Use the Two-Pointer Insight

- Keep `left`, `right`, `left_max`, and `right_max`.
- Update the maximum for the side you move.
- If the current bar is lower than that side's maximum, add the difference to the answer.

Accumulate Water While Moving Inward

- This version handles empty or very small arrays naturally because the loop does not run.
- Each bar is visited at most once.
- Time complexity is O(n), and extra space complexity is O(1).