Can anyone please explain how to solve this question. The link I mentioned already has a solution but the most efficient on takes O(N) time and O(N) space, I need a solution that takes O(N) time and O(1) space.
@vijju123 @neilit guys please help me out.
Is this related to graph theory? Cause I have no experience of graph theory as of yet dear. Sorry 
It is simple array based question, this link has the awesome explains very nicely. http://www.geeksforgeeks.org/trapping-rain-water/
I will give it a look in evening (have classes atm-college… )
In this problem if we find the highest bar on left and right side of the current bar, than the amount of water current bar can hold will be ={min(left_max,right_max)-height[cur]}
It can be done by using two pointers.
int TrappingWater(int height[],int n)
{
int left_max=0,right_max=0,ans=0;
int left=0,right=n-1;
while(left<=right)
{
if(height$<$height[right])
{
if(height>=left_max) left_max=height;
else ans+=left_max-height;
++left;
}
else
{
if(height[right]>=right_max) right_max = height[right];
else ans+=right_max - height[right];
–right;
}
}
return ans;
}
How would you deal with cases like-
{3,0,0,5,0,0,4,0,0,3} ??
Meaning a central maximum and adjacent minimums
@arpit728 The amount of water that will be on top of any index is determined by the left max and right max for that index. The left max and right max acts as container and the amount of water on top of any index = min(H[left_max], H[right_max]) - H[index].
Now lets divide the array in two parts using the max H… let it be at indMaxH. For all index < indMaxH … the left “wall” and for all index > indMaxh the right wall will determine the water. I am not posting any code. Think over it and you can easily write the code with O(n) time and O(1) space complexities.
And how will we determine the left wall for every index < indMaxH and right wall for every index > indMaxH .
@please explain your logic, I found similar code on leetcode too but didn’t understand how does it work.
for left wall just traverse from left and keep the max height seen so far as left wall. Similarly for right wall.
please explain your logic, I found similar code on leetcode too but didn’t understand how does it work.