Leetcode 42 Trapping rain water - mock interview on interviewing.io Feb 21, 2020 10:00 PM

Leetcode42TrappingRainWater.cs

using System;

// To execute C#, please define "static void Main" on a class
// named Solution.
/*


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.

height = [0,1,0,2,1,0,1,3,2,1,2,1]
prefix    0,0,1,1,2,2,2,2,3,3,3,3
suffix    3,3,3,3,3,3,3,2,2.2,1.0
water     0,0,1,0,1,2,1,0,0,1,0,0 
sum = 6 
go through min(0,3) > 0 -> 
O(N)

[0,1,0,2,1]
[3,1,2,5]
     - highest bar
   3  right 5 - min (3,5) = 1 water
iterate the number in the array from left to right   
 3
 1 -> 3, 5 , hold 3 -1 = 2
 2 -> 3, 5, hold 3 - 2 = 1
 5 -> 3, 0, < 5 -> 0
 sum = 3 
 return 3
 
*/
class Solution
{
    static void Main(string[] args)
    {
        var test = new Solution();
        var result = test.CalTrapWater(new int[]{0,1,0,2,1,0,1,3,2,1,2,1});
        
       // for (var i = 0; i < 5; i++)
        { 
            Console.WriteLine("water is " + result.ToString());
            
        }
    }
    
    ///[0, 1, 0, 2, 1] - line 19 to line 29 - return 3
    /// time: O(N)
    /// space: O(N)
    /// 
    public int CalTrapWater(int[] nums)
    {
        if(nums == null || nums.Length <= 2)
            return 0; 
        
        var n = nums.Length;
        var prefix = new int[n];  // default 0 
        var suffix = new int[n];
        //
        //
        var max = 0; 
        for(int i = 0; i < n; i++)  // i = 1
        {
            prefix[i] = Math.Max(max, nums[i]); // prefix[1] = 0, prefix[2] = 1, prefix[3] = 1, prefix[4] = 2
            max = prefix[i]; 
        }
        
        max = 0; 
        for(int i = n -1 ; i >= 0; i--)
        {
            suffix[i] = Math.Max(max, nums[i]);// s[4] = 0, suffix[3] = 1, s[2] = 2, s[1] = 2, s[0] = 2
            max = suffix[i];
        }
        
        var water = 0; 
        for(int i = 0; i < n; i++)
        {
            max = Math.Min(prefix[i], suffix[i]); //i = 2, water = 1, 
            if(max > nums[i])
               water += max - nums[i];                                                             
                               
        }
                               
        return water;                                
    }
}