/**
 * For each bar, the max rain that it could trap depends on the shorter height of left and right bars
 *     which is the highest bar it could reach.
 *
 * Travel from left to right to find the left blocking bar for each bar, then travel from right to left
 *     to find the bar on right side. At the end find the shorter one, and subtract the origin height
 */


int TrappingRainWater(int eMap[], int n)
{
    if (n < 3) return 0;
    int limit[n]; 

    int rain = 0;

    int maxHeight = 0;
    for (int i = 0; i < n; ++i) 
    {
        if (maxHeight < eMap[i])
            maxHeight = eMap[i];

        limit[i] = maxHeight;
    }

    maxHeight = 0;
    for (int i = n-1; i >= 0; --i) 
    {
        if (maxHeight < eMap[i])
            maxHeight = eMap[i];

        if (maxHeight < limit[i])
            limit[i] = maxHeight;

        rain += limit[i] - eMap[i];
    }


    return rain;
}

#include <stdio.h>
int main(int argc, char** argv)
{
    int a[] = {0,1,0,2,1,0,1,3,2,1,2,1}; // rain = 6;
    int b[] = {6,4,2,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,3}; // rain = 83
    int sizeOfInt = sizeof(int);

    int rain = TrappingRainWater(a, sizeof(a)/sizeOfInt);
    printf("%d\n", rain);

    rain = TrappingRainWater(b, sizeof(b)/sizeOfInt);
    printf("%d\n", rain);

    return 0;
}