# LeetCode 42: Trapping Rain Water

## Problem Restatement

We are given an array `height`.

Each value represents the height of a vertical bar. Every bar has width `1`.

After rain falls, water can be trapped between taller bars. We need to compute the total amount of trapped water.

The official statement says: 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:

```python
height = [0,1,0,2,1,0,1,3,2,1,2,1]
```

The answer is:

```python
6
```

Another example:

```python
height = [4,2,0,3,2,5]
```

The answer is:

```python
9
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | An array `height` of non-negative integers |
| Output | Total units of trapped rain water |
| Bar width | Each bar has width `1` |
| Constraint | Need an efficient linear-time solution |

Function shape:

```python
def trap(height: list[int]) -> int:
    ...
```

## Key Observation

At any index `i`, water can stay above `height[i]` only if there is a wall on the left and a wall on the right.

The water level at index `i` is controlled by the shorter of the tallest left wall and the tallest right wall.

So the water above index `i` is:

```python
min(max_left, max_right) - height[i]
```

If this value is negative, it contributes `0`.

For example:

```python
height = [0, 2, 0, 3]
```

At index `2`, the height is `0`.

The tallest wall on the left is `2`.

The tallest wall on the right is `3`.

The water level is limited by the shorter wall, which is `2`.

So index `2` can hold:

```python
2 - 0 = 2
```

units of water.

## First Thought: Precompute Boundaries

A direct efficient solution is to precompute two arrays.

`left_max[i]` stores the tallest bar from index `0` to index `i`.

`right_max[i]` stores the tallest bar from index `i` to the end.

Then for each index `i`, the trapped water is:

```python
min(left_max[i], right_max[i]) - height[i]
```

Code:

```python
class Solution:
    def trap(self, height: list[int]) -> int:
        n = len(height)

        left_max = [0] * n
        right_max = [0] * n

        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])

        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        water = 0
        for i in range(n):
            water += min(left_max[i], right_max[i]) - height[i]

        return water
```

This solution is correct and runs in `O(n)` time.

The problem is that it uses `O(n)` extra space.

We can do better.

## Key Insight

We do not need to store every left and right maximum.

We can keep two pointers:

```python
left = 0
right = len(height) - 1
```

We also keep:

```python
left_max = 0
right_max = 0
```

At each step, compare `height[left]` and `height[right]`.

If `height[left] < height[right]`, then the left side is the limiting side. There is already a right wall at least as tall as `height[left]`, so the trapped water at `left` depends only on `left_max`.

If `height[right] <= height[left]`, then the right side is the limiting side. There is already a left wall at least as tall as `height[right]`, so the trapped water at `right` depends only on `right_max`.

This lets us process one side at a time.

## Algorithm

Initialize:

```python
left = 0
right = len(height) - 1
left_max = 0
right_max = 0
water = 0
```

While `left < right`:

If `height[left] < height[right]`:

1. Update `left_max`.
2. Add `left_max - height[left]`.
3. Move `left` rightward.

Otherwise:

1. Update `right_max`.
2. Add `right_max - height[right]`.
3. Move `right` leftward.

The update order matters.

We update the boundary maximum before adding water.

That guarantees we never add a negative amount.

## Walkthrough

Use this input:

```python
height = [4, 2, 0, 3, 2, 5]
```

Start:

```python
left = 0
right = 5
left_max = 0
right_max = 0
water = 0
```

Since `height[left] = 4` and `height[right] = 5`, process the left side.

At index `0`, update:

```python
left_max = 4
```

Water added:

```python
4 - 4 = 0
```

Move `left` to index `1`.

At index `1`, height is `2`.

The right side still has a wall of height `5`, so the left boundary controls this position.

Water added:

```python
4 - 2 = 2
```

Move `left`.

At index `2`, height is `0`.

Water added:

```python
4 - 0 = 4
```

Move `left`.

At index `3`, height is `3`.

Water added:

```python
4 - 3 = 1
```

Move `left`.

At index `4`, height is `2`.

Water added:

```python
4 - 2 = 2
```

Total:

```python
0 + 2 + 4 + 1 + 2 = 9
```

So the answer is:

```python
9
```

## Correctness

For each index, the trapped water depends on the smaller of the tallest wall on the left and the tallest wall on the right.

When `height[left] < height[right]`, there is a right boundary that is taller than `height[left]`. Therefore, for the current `left` index, the amount of water is determined by the best left boundary seen so far, `left_max`.

If `left_max` is higher than `height[left]`, the difference is trapped water. If not, the current bar becomes the new left boundary.

The same argument applies symmetrically when processing the right side.

Each step finalizes one index. Once an index is processed, its trapped water amount will not change, because the algorithm only processes a side when the opposite side already provides a sufficient boundary.

Therefore, every index contributes exactly the correct amount of trapped water, and the total sum is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each pointer moves inward at most `n` total steps |
| Space | `O(1)` | Only a few variables are used |

## Implementation

```python
class Solution:
    def trap(self, height: list[int]) -> int:
        left = 0
        right = len(height) - 1

        left_max = 0
        right_max = 0
        water = 0

        while left < right:
            if height[left] < height[right]:
                left_max = max(left_max, height[left])
                water += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                water += right_max - height[right]
                right -= 1

        return water
```

## Code Explanation

The two pointers begin at the ends of the array:

```python
left = 0
right = len(height) - 1
```

The variables `left_max` and `right_max` store the best walls seen so far from each side.

```python
left_max = 0
right_max = 0
```

The loop continues while there are unprocessed bars between the two pointers:

```python
while left < right:
```

If the left bar is lower than the right bar, the left side is safe to process:

```python
if height[left] < height[right]:
```

We update the best left wall:

```python
left_max = max(left_max, height[left])
```

Then we add trapped water at this index:

```python
water += left_max - height[left]
```

If the current bar is the tallest so far, this adds `0`.

Otherwise, it adds the difference between the left boundary and the current height.

The right side is handled the same way:

```python
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
```

At the end, `water` contains the total trapped rain water.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
    assert s.trap([4,2,0,3,2,5]) == 9
    assert s.trap([0]) == 0
    assert s.trap([0, 1, 2, 3]) == 0
    assert s.trap([3, 2, 1, 0]) == 0
    assert s.trap([2, 0, 2]) == 2
    assert s.trap([3, 0, 0, 2, 0, 4]) == 10

    print("all tests passed")

run_tests()
```

| Test | Expected | Reason |
|---|---:|---|
| `[0,1,0,2,1,0,1,3,2,1,2,1]` | `6` | Standard example |
| `[4,2,0,3,2,5]` | `9` | Deep valley with rising right wall |
| `[0]` | `0` | One bar cannot trap water |
| `[0,1,2,3]` | `0` | Increasing heights cannot trap water |
| `[3,2,1,0]` | `0` | Decreasing heights cannot trap water |
| `[2,0,2]` | `2` | Simple bounded valley |
| `[3,0,0,2,0,4]` | `10` | Multiple trapped regions |