Given n non-negative integers representing an elevation map where the width of each bar is 1,
compute how much water it is able to
trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case,
6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

keywords:
integer array, arr[i] >= 0 for any i, representing width of each bar = 1, height[i] = arr[i]
ask: how much water it is able to trap after raining



         ---
   ---      ---
---   ---      ---

brute force solution ->left = 1, right = 2, itself = 0, naive store min(left, right) - arr[i] -> O(n)
time complexity: O(n^2)  - brute force - efficient
[2, 1, 0, 1, 3]
-> 3
[0, 1, 2, 1, 0]
->
[4, 1, 0, 1, 3]
->
[0, 3, 4, 3, 1]
-> left to right
-> right to left
-> get minimum for two iteration, find the sum O(n)
descending stack: [2, 1, 0,] -> maximum height = 2
ascending stack: [0, 1, 3] -> maximum height = 3

-> left to right linear time complexity ->
[3, 4, 5] -> descending order
[5, 6, 7]
range from index = 3 to 7, height -> water height = min(2, 3) = 2




public int trap(int[] height) {
   if(height == null)
     return 0;

  var length = height.Length();


	// two iterations - left to right
  //[2, 1, 0, 1, 3]
  //-> 3
  //[0, 1, 2, 1, 0]

  var leftToRight = ScanFromLeftToRight(height);
  var rightToLeft = ScanFromLeftToRight(Array.Reverse(height));  // <- [1, 2, 3]  -> [3, 2, 1] -> left to right
  rightToLeft = Array.Reverse(rightToLeft);


  // get the minimum of both
  for()

  // get the sum of two array
}

private static int[] ScanFromLeftToRight(int[] height)
{
  var leftToRight = new int[length];
  var max = height[0];
  for(int index = 0; index < length; index++)
  {
    var current = leftToRight[index];
    if(current > max)
    {
      max = current;
      leftToRight[index] = 0;
    }
    else
    {
      leftToRight[index] = max - current;
    }
  }

  return leftToRight;
}