Daily Dose of DSA- Day 9

//Question link : https://leetcode.com/problems/trapping-rain-water/
// /*In this approach we traverse the array and
// for every element we search for leftmax(traversing in the left)and rightmax(traversing in the right).
// Then water trapped at a particular i  will be {min(lmax,rmax)-array element}. At the same time we keep adding the resultant water.*/

class Solution
{
public:
    int trap(vector<int> &height) // naive approach TC θ(n^2) SC O(1)
    {
        int water = 0;
        int n = height.size();
        // traversing the array
        for (int i = 1; i < n - 1; i++) // first and last element does not have water stored
        {
            int lmax = height[i];
            for (int j = 0; j < i; j++)
                lmax = max(lmax, height[j]); // lmax search

            int rmax = height[i];
            for (int j = i + 1; j < n; j++)
                rmax = max(rmax, height[j]); // rmax search

            water = water + (min(lmax, rmax) - height[i]); // for every iteration we keep updating the water
        }

        return water;
    }
};
// Time limit will exceed as it is θ(n^2) we need to optimize the solution
// In this approach we precompute prfixmax and suffixmax array ,
// then for every iteration we know the leftmax and rightmax of that position.
// Then we keep updating the resultant as + {min(lmax,rmax)-array element}
class Solution
{
public:
    int trap(vector<int> &height) // better approach (
    {
        long long water = 0;
        long long n = height.size();
        int lmax[n], rmax[n]; // computing the prefixmax and suffixmax array

        lmax[0] = height[0];
        for (int i = 1; i < n; i++) // prefixmax calculation
        {
            lmax[i] = max(height[i], lmax[i - 1]);
        }

        rmax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) // suffixmax calculation
        {
            rmax[i] = max(height[i], rmax[i + 1]);
        }

        for (int i = 1; i < n - 1; i++) // finally calculating res with the prefixmax and sffixmax arrays
        {
            water = water + (min(lmax[i], rmax[i]) - height[i]);
        }

        return water;
    }
};
// Using two pointer approach
/*this method is based on intuition , .
while checking in the 2 main cases that is there any greater right present or greater left present we encounter 2 subcases
if that element is greater then maxleft we update the maxleft else we do maxleft-present element and increment the pointer . Similarly for right ,
if we encounter right greater than maxright we update the maxright else we do maxright-present element and decrement the pointer.*/
class Solution
{
public:
    int trap(vector<int> &height)
    {
        int n = height.size();
        int left = 0, right = n - 1;
        int water = 0;
        int maxleft = 0, maxright = 0;

        while (left <= right)
        {
            if (height[left] <= height[right]) // condition to check is there any greater right present
            {
                if (height[left] >= maxleft) // update the maxleft
                {
                    maxleft = height[left];
                }

                else
                {
                    water += maxleft - height[left]; // if that height is smaller then maxleft we return maxleft-present
                }

                left++;
            }

            else // will cover the cases in  which greater right present
            {
                if (height[right] >= maxright) // update the maxright
                {
                    maxright = height[right];
                }
                else
                {
                    water += maxright - height[right]; // if that height is smaller than maxright we return maxright-present
                }
                right--;
            }
        }

        return water;
    }
};