hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Trapping Rain Water


  • Approach:

    1. Define two arrays say, maxLeft, maxRight.

    2. Assign height[0] as maxLeft[0] and height[N-1] as maxRight[N-1].

    3. Traverse from i = 1 to N-1.

    4. For each of the i, calculate maxLeft[0] to maxLeft[i] cumulatively.

    5. Similarly, calculate maxRight[n-i-1] to maxRight[n-i] cumulatively.

    6. Now that we have maxLeft and maxRight from each of the ith positions.

    7. For each i, calculate the minimum of maxLeft[i] and maxRight[i].

    8. Subtract the height of ith elevation from the minimum value.

    9. Add that subtracted value to the Ans.

    10. Return the Ans.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(N)


Code [C++]

class Solution {

public:

int trap(vector<int>& height) {

int n = height.size();

vector<int>maxLeft(n, 0);

vector<int>maxRight(n, 0);

maxLeft[0] = height[0], maxRight[n-1] = height[n-1];

for(int i=1; i<n; i++){

maxLeft[i] = max(height[i], maxLeft[i-1]);

maxRight[n-i-1] = max(height[n-i-1], maxRight[n-i]);

}

int ans = 0;

for(int i=0; i<n; i++){

int minMax = min(maxLeft[i], maxRight[i]);

ans += (minMax - height[i]);

}

return ans;

}

};