Trapping Rain Water

Edit Distance

Product of Array Except Self

Compute water trapped between elevation bars after rainfall.

Each non-negative value in `height` is a unit-width elevation bar. Return the total water units retained after rain.

**Input / output**
- Input: `height: integer[]`
- Output: integer water volume

**Examples**
1. `[0,1,0,2,1,0,1,3,2,1,2,1]` returns `6`.
2. `[4,2,0,3,2,5]` returns `9`.

**Constraints**
- `0 <= height.length <= 100,000`
- `0 <= height[i] <= 100,000`

**Follow-up**
Derive the two-pointer rule from the smaller of the left and right maxima.

- 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).