42. Trapping Rain Water

Hard https://www.geeksforgeeks.org/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

Solution 1:
Traverse every element, find the highest bar on the left side and right side. take the smaller of two highest height, the different between smaller height and the current height is the amount of the water can be stored in this element. time complexity is O(n2)

Solution2:
pre-compute the highest bar of the left side and right side of each element in O(n).

    public int trap(int[] height) {
        int n = height.length;
        if(n == 0) return 0;
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = height[0];

        // left[i] contains height of tallest bar from 0 to i include itself.
        for(int i = 1; i < n; i++){
            left[i] = Math.max(left[i-1],height[i]);//left highest include current element.
        }
        // left[i] contains height of tallest bar from i to n-1 include itself.
        right[n-1] = height[n-1];
        for(int i = n - 2; i >=0; i--){
            right[i] = Math.max(right[i+1],height[i]);
        }
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += Math.min(left[i],right[i]) - height[i];
        }
        return sum;
    }

Solution 3:
two pointer.
1) compare head and tail, which is smaller, move into the middle. low++ or high--
2) if hight[high] > height[low]
    if height[low] > maxL  need to get the different between maxL and height[low]. because height[high] must be larger than maxL. maxL is the smaller of the highest of the left side and the right side on element low.
    if height[low] < maxL, assgin the current value to maxL.
    low++ move to the middle.

    public int trap(int[] height) {
        if(height == null || height.length == 0) return 0;
        int high = height.length -1,low = 0;
        int maxL = 0;
        int maxR = 0;
        int sum = 0;
        while(low <= high){
            if(height[high] > height[low]){
                if(height[low] > maxL){
                    maxL = height[low];
                }else{
                    sum += (maxL - height[low]);
                }

                low++;

            }else{
                if(height[high] > maxR){
                    maxR = height[high];
                }else{
                    sum += (maxR - height[high]);
                }

                high--;
            }
        }
        return sum;
    }