Table of Contents

## Problem

Given `n`

non-negative integers representing an elevation map where the width of each bar is `1`

, compute how much water it can trap after raining.

## Sample input

heights: [0, 8, 0, 0, 5, 0, 0, 10, 0, 0, 1, 1, 0, 3]

## Sample output

The output for the sample input is 48. In the above diagram, water can only be trapped from elevation bar 8 to 10 and from 10 to 3. Each bar from elevation bar 8 to 10 is subtracted from 8 to get the difference (i.e 8, 8, 3, 8, 8), and each bar from elevation bar 10 to 3 is subtracted from 3 to get the difference (i.e 3, 3, 2, 2, 3) and both differences are added up to get how much rain it can trap or the water area i.e 8+8+3+8+8+3+3+2+2+3 == 43. Note that since each elevation bar has its width as 1, it is safe to ignore the width is calculating the water area.

## Solution algorithm explanation

The explanation of the solution algorithm is simple. Looking at the image, one can quickly see that for water to be trapped, there has to be a minimum of two elevation bars that are higher than all other bars in between them.

So what i have done in this algorithm is to first of all look for the tallest bar from the given heights array. Once i find the peak bar, i go from the leftmost bar to the peak bar looking to see if i find the first bar whose height is not equal to 0; once i find that bar whose height is not 0 (which i call front in my code), starting from the position of that bar, i begin to calculate the difference between front and the next bar (only if next bar is shorter than front), totaling the differences; if next bar is taller than front, i make that next bar the new front. All the differences from front to the peak bar in my code is assigned to a variable sumfront.

After this round, i do the exact same thing for the elevation bars starting from the end of the heights array to the peak value but this time instead i store the first bar whose height is not 0 in a variable called back and all differences are totaled and assigned to a variable called sumback in my code. In going towards the peak value, if i find any bar taller than the current back value, i make that bar the new back.

After every thing i sum up sumfront and sumback and the result of it is the water area or how much water that can be trapped within our elevation bars.

## Code in c++

```
int waterArea(vector<int> heights) {
// Write your code here.
int front=-1e9, back=-1e9, maxz=-1e9, maxindx, sumfront=0, sumback=0;
if(heights.size() == 0) return 0;
for(int i=0;i<heights.size();i++){
if(heights[i] > maxz){
maxz = heights[i];
maxindx = i;
}
}
for(int i=0;i<maxindx;i++){
if(front == -1e9){
if(heights[i] > 0){
front=heights[i];
}else{
continue;
}
}
if(front > heights[i]){
sumfront += front - heights[i];
}else{
front = heights[i];
}
}
for(int i=heights.size()-1;i>maxindx;i--){
if(back == -1e9){
if(heights[i] > 0){
back=heights[i];
}else{
continue;
}
}
if(back > heights[i]){
sumback += back - heights[i];
}else{
back = heights[i];
}
}
return sumfront + sumback;
}
```

## Time and space complexity

O(n) time | O(1) space