Stack #1 Trapping Rain Water
Problem Statement: here
Solution -
Water will be bounded if there exist two piles at index i and j where |j-i| > 1.
So, we will use a stack to answer this question.
The principle used is:
- Push into stack, if the current element is smaller than the stack top. This ensures that the current element is bounded by the stack top from left side.
- Once we encounter that current element is larger than the stack top, then we have got the upper bound for stack top. So, since the stack top is bounded from both sides, we exactly know that we can fill min(left max, right max) in this. But wait, there are some clarifications. The stack top, for which we have got this boundation, it is the minimum level above which we have filled water as of now. Below this level, we have filled all the water. So, the maximum water we can fill in this range will be min(left max, right max) - current value. Also, since we are filling it in a given range, we will actually add (min(left max, right max) - current value)*(right ind - left ind - 1) to our answer
- This might be bit complicated, but when you will go through code, you will better understand it.
A neat explanation is available here: here
Also, note that we can solve this using DP, but this method of using stack is important, as we gonna see ahead some similar uses of stacks! So make yourself comfortable with this.
Code for reference:
Link to submission on LeetCode - here
class Solution {
public:
int trap(vector<int>& heights) {
int n = heights.size();
if (n<2) return 0;
int ind = 0;
while (heights[ind] == 0 && ind+1<n) ind++;
// push into stack if current element is smaller than top.
// pop if it is greater.
int ans = 0;
stack<int> stk;
for(int i=ind;i<n;i++){
if (stk.empty()){
stk.push(i);
}
else{
if (heights[i] <= heights[stk.top()]){
stk.push(i);
}
else{
while(heights[i] > heights[stk.top()]){
int low = stk.top();
stk.pop();
if (stk.empty()){
break;
}
else{
ans += (min(heights[stk.top()],heights[i]) - heights[low])*(i - stk.top() - 1);
}
}
stk.push(i);
}
}
}
return ans;
}
};
What next ??
Try out the harder version of this problem - here
I will share the link to my solution and explanation over here, once I post it, since it does not involve stacks, it will be not tagged under this category!
No comments:
Post a Comment