30 Days of Code [Day 10]

23 Aug 2021

QUESTION : 42. Trapping Rain Water

Time Complexity : O(n) Space Complexity : O(2n)

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vi left(n), right(n);
        left[0] = height[0];
        fo(i,1,n) left[i] = max(left[i-1], height[i]);
        right[n-1] = height[n-1];
        of(i,n-1,0) right[i] = max(right[i+1], height[i]);
        int res = 0;
        fo(i,1,n-1) res += (min(left[i], right[i]) - height[i]);
        return res;
    }
};

ANOTHER SOLUTION

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int lmax = 0, rmax = 0;
        int l,r;
        l = 0;
        r = n-1;
        int res = 0;
        while(l <= r){
            if(height[l] <= height[r]){
                if(lmax < height[l]) lmax = height[l];
                else{
                    res += (lmax - height[l]);
                }
                l++;
            }
            else{
                if(rmax < height[r]) rmax = height[r];
                else{
                    res += (rmax - height[r]);
                }
                r--;
            }
        }
        return res;
    }
};