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.

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)

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)

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)

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)