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
Problem: 42. Trapping Rain Water
Problem Link:
Companies Asked: Samsung, Amazon, Uber, Visa, Apple, Adobe, Intel, Tesla, Google, Rubrik, Oracle, Paypal, Intuit, Citadel, Sapient, Facebook, Snapchat, Bloomberg, Microsoft, Qualtrics, ServiceNow, Goldman Sachs, National Instruments
Approach:
Define two arrays say, maxLeft, maxRight.
Assign height[0] as maxLeft[0] and height[N-1] as maxRight[N-1].
Traverse from i = 1 to N-1.
For each of the i, calculate maxLeft[0] to maxLeft[i] cumulatively.
Similarly, calculate maxRight[n-i-1] to maxRight[n-i] cumulatively.
Now that we have maxLeft and maxRight from each of the ith positions.
For each i, calculate the minimum of maxLeft[i] and maxRight[i].
Subtract the height of ith elevation from the minimum value.
Add that subtracted value to the Ans.
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;
}
};