trapping rain water explanation

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