Leetcode Problem 42 Trapping Rain Water.txt

42. Trapping Rain Water
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

Hint to solve: Create a left mask, right mask.
Add both the mask by selecting the min from both.
Subtract the original mountian from additive mask.

public class Solution {
    public int Trap(int[] height) 
    {
        //won't be able to hold any water
        if(height.Count() == 0 || height.Count() == 1)
            return 0;
        
        int[] leftMask = new int[height.Count()];
        int[] rightMask = new int[height.Count()];
        
        int leftMax = height[0];
        for(int i = 0; i<height.Count(); ++i)
        {
            int current = height[i];
            if(current > leftMax)
            {
                leftMax = current;
            }
            leftMask[i] = leftMax;
        }
        
        int rightMax = height[height.Count()-1];
        for(int i = height.Count()-1; i>=0; --i)
        {
            int current = height[i];
            if(current > rightMax)
            {
                rightMax = current;
            }
            rightMask[i] = rightMax;
        }
        
        
        int[] additiveMask = new int[height.Count()];
        for(int i = 0; i<height.Count();++i)
        {
            additiveMask[i] = Math.Min(leftMask[i],rightMask[i]);
        }
        
        
        int totalWaterTrapped = 0;
        
        for(int i = 0; i<height.Count();++i)
        {
            totalWaterTrapped += (additiveMask[i]-height[i]);
        }
        
        
        return totalWaterTrapped;
        
        
    }
}