# 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>

![](https://1416717093-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-ME49AWTsL3PV5O3FW36%2F-MLusP4a3x_0BEsrjaEc%2F-MLusp7LmaNQOfPl601B%2Frainwatertrap.png?alt=media\&token=03f109cf-2119-443a-af06-f79ac13fcea7)

```
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)**
