# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/sliding-window/hard/42.-trapping-rain-water.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.