> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/array_and_string/two-pointers/lr-pointers/trapping-rain-water.md).

# Trapping Rain Water

## Question ([LC.42](https://leetcode.com/problems/trapping-rain-water/))

> Given an integer array representing the height of n unit width bars, find volume of rain water it can trap.

## Example

```
I: [0,1,2]
O: 0
I: [3,1,2]
O: 1
I: [0,1,0,2,1,0,1,3,2,1,2,1]
O: 6
```

## Analysis

The water being trapped inside any bar is determined by the highest left and right bar.\
The volume of water trapped = min(left, right) - height

## Brute Force Three Pass

We can assign the highest left bars, assign the highest right bars, then compute the rain water.

```java
public int trap(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    int n = height.length;
    int[] leftBars = new int[n];
    int[] rightBars = new int[n];
    // assign left bars
    int left = 0;
    for (int i = 0; i < n; i++) {
        left = Math.max(left, height[i]);
        leftBars[i] = left;
    }
    // assign right bars
    int right = 0;
    for (int i = n - 1; i >= 0; i--) {
        right = Math.max(right, height[i]);
        rightBars[i] = right;
    }
    // compute the rain volume
    int rain = 0;
    for (int i = 1; i < n - 1; i++) {
        int current = Math.min(leftBars[i], rightBars[i]) - height[i];
        rain += current > 0 ? current : 0;
    }
    return rain;
}
```

Time O(3n) = O(n) Space O(2n) = O(n)

## L/R Pointers

Linear time is probably as good as we can get. Unless we can do a binary search on the array. But the space can be further optimized.

We maintain two values leftBar and rightBar. Then use left/right pointers to update on the way.

```
leftBar
rightBar

left -->     <--- right

move left if leftBar is lower than rightBar
move right if rightBar is lower than the leftBar
(so we make sure water can be trapped by the lower end)
```

```java
public int trap(int[] height) {
    if (height == null || height.length < 2) {
        return 0;
    }
    int rain = 0;
    int left = 0, right = height.length - 1;
    int leftBar = height[left], rightBar = height[right];
    while (left < right) {
        if (leftBar < rightBar) {
            rain += leftBar - height[left];
            left++;
            leftBar = Math.max(leftBar, height[left]);
        } else {
            rain += rightBar - height[right];
            right--;
            rightBar = Math.max(rightBar, height[right]);
        }
    }
    return rain;
}
```

Time O(n) Space O(1)

## Follow Up ([LC.407](https://leetcode.com/problems/trapping-rain-water-ii/description/))

Trap rain water 3D version