# 20.Trapping Rain Water

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

![](/files/-MLusp7LmaNQOfPl601B)

```
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
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.
```

## Solution I: (Brute Force)

**Approach:** \
**Finding the left max and right max from a point.**\
**Finding water level by subtracting height from min(left max , right max)**

```cpp
class Solution
{
public:
    int trap(vector<int> &height)
    {

        int s = 0;
        for (int i = 0; i < height.size(); i++)
        {

            int lMax = 0;
            int rMax = 0;

            for (int j = i; j >= 0; j--)
            {
                if (height[j] > lMax)
                {
                    lMax = height[j];
                }
            }

            for (int j = i; j < height.size(); j++)
            {
                if (height[j] > rMax)
                {
                    rMax = height[j];
                }
            }

            int x = min(lMax, rMax) - height[i];
            if (x > 0)
            {
                s = s + x;
            }
        }
        return s;
    }
};
```

**Time Complexity: O(N^2)**

## Solution II: (DP)

```cpp
class Solution
{
public:
    int trap(vector<int> &height)
    {

        int n = height.size();

        if (n == 0)
        {
            return 0;
        }

        vector<int> lm(n, 0);
        vector<int> rm(n, 0);

        lm[0] = 0;
        int lh = height[0];
        for (int i = 1; i < n; i++)
        {
            lm[i] = lh;
            lh = max(lh, height[i]);
        }

        rm[n - 1] = 0;
        int rh = height[n - 1];
        for (int i = n - 2; i >= 0; i--)
        {
            rm[i] = rh;
            rh = max(rh, height[i]);
        }

        int water = 0;
        for (int i = 0; i < n; i++)
        {
            int amount = min(lm[i], rm[i]) - height[i];
            water += (amount > 0) ? amount : 0;
        }

        return water;
    }
};
```

**Time Complexity: O(N)**

## Solution III: (Two Pointer)

```cpp
class Solution
{
public:
    int trap(vector<int> &height)
    {

        int s = 0;
        int lMax = 0;
        int rMax = 0;

        int l = 0;
        int r = height.size() - 1;

        while (l < r)
        {
            if (height[l] < height[r])
            {
                if (height[l] >= lMax)
                {
                    lMax = height[l];
                }
                else
                {
                    s = s + lMax - height[l];
                }
                l++;
            }
            else
            {
                if (height[r] >= rMax)
                {
                    rMax = height[r];
                }
                else
                {
                    s = s + rMax - height[r];
                }
                r--;
            }
        }
        return s;
    }
};
```

**Time Complexity: O(N)**


---

# 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://soumyajit4419.gitbook.io/ds-algo/arrays/22.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.