> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/sliding-window/hard/42.-trapping-rain-water.md).

# 42. Trapping Rain Water

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png)

<pre><code><strong>Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
</strong><strong>Output: 6
</strong><strong>Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: height = [4,2,0,3,2,5]
</strong><strong>Output: 9
</strong></code></pre>

&#x20;

**Constraints:**

* `n == height.length`
* `1 <= n <= 2 * 104`
* `0 <= height[i] <= 105`

## Intuition

```
Approach 1:
BruteForce

We at each index, Find Left_max, Right_max
Take min(Left_max, Right_max) - arr[i]
This gives tapped water for a particular index

This is N^2

Approach 2:
Better

Rather than Going and finding the Left_max and Right_max again and again
We, Maintain a Prefix_max and Suffix_max array and Do it in 1 time

This has a 
Time = N, Space = N for Matintaing array





Approach 3:
Optimal

Maintain Two pointers, 
Here, We maintain Left max and Right max 
Now we do
L_max - arr[low]
only when we ensure that there is at least that much on right side

eg-> l =3(2), r=10(2)
Now it enters if condition and Ensures that low<=high
Meaning atleast 2 is present on right side

then when 
l=4(1), r10(2)
We know for sure that right has 2 or greater than 2
Hence we directly take l_max = 2 - arr[low]

rather than min(l_max, r_max) - arr[i]
where r_max >= l_max we know 
Hence no need of it, 

similarly for right side
```

### Links

<https://leetcode.com/problems/trapping-rain-water/description/>

### Video Links

<https://www.youtube.com/watch?v=m18Hntz4go8&ab_channel=takeUforward>

### Approach 1:

```
Better
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int trap(vector<int>& arr) {
        int n = arr.size();
        vector<int> pre(n,-1), suf(n,-1);
        for(int i=0; i<n; i++){
            if(i==0)
                pre[i] = arr[i];
            else
                pre[i] = max(pre[i-1], arr[i]);
        }

        for(int i=n-1; i>=0; i--){
            if(i==n-1)
                suf[i] = arr[i];
            else
                suf[i] = max(suf[i+1], arr[i]);
        }

        int ans=0;
        for(int i=0; i<n; i++){
            ans += min(pre[i], suf[i]) - arr[i];
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
Optimal
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int trap(vector<int>& arr) {
        int n = arr.size();
        int low=0, high=n-1, l_max=0, r_max=0, ans=0;

        while(low<=high){
            if(arr[low]<=arr[high]){
                if(arr[low]>=l_max)
                    l_max = arr[low];
                else
                    ans += l_max-arr[low];
                low++;
            }
            else{
                if(arr[high]>=r_max)
                    r_max = arr[high];
                else
                    ans += r_max-arr[high];
                high--;
            }
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###