# C++ O(n) time O(1) space 9ms solution

• From beginning, find the next bar which is higher than the current bar, calculate the `total water`, do it recursively till end.

``````    int trap(vector<int>& height) {
if(height.size()==0) return 0;
return trapHelper(height,0);
}

int trapHelper(vector<int>& height,int begin){
if(begin>=height.size()-1) return 0;
while(height[begin+1]>=height[begin]) begin++;
if(begin>=height.size()-1) return 0;
int i=begin+1;
int maxHeight=-1;
int maxAt=0;
while(height[i]<height[begin]&&i<height.size()){
if(height[i]>maxHeight){
maxHeight=height[i];
maxAt=i;
}
i++;
}
if(i<height.size()) return calArea(height,begin,i,height[begin])+trapHelper(height,i);
else return calArea(height,begin,maxAt,maxHeight)+trapHelper(height,maxAt);
}

int calArea(vector<int>& height,int begin,int end,int maxHeight){
int sum=0;
for(int i=begin+1;i<end;i++)
sum+=maxHeight-height[i];
return sum;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.