Pour water over a histogram. Find the amount of water accumulated in the gaps.

HistogramFillWater.java

/*
Image URL for representation :http://www.darrensunny.me/wp-content/uploads/2014/04/Rain-Water-Trap.png

Algo: From  left  compute the max of the current element and the elements on the left. and store in array : maxLeft[]
From right move left and compute the max of current element and the element on right 
for each element and store in array: maxRight[].

The amount of water above each element is Min(maxleft[i],maxRight[i])-hist[i].

Assumption width of each histogram bar is 1.

Time complexity: O(n).
**/

public int getWaterinHistogram(int[] hist)
{
    if(hist==null||hist.length==0||hist.length==1)
        return 0;
    
    int [] maxLeft= new int[hist.length];
    int [] maxRight= new int[hist.length];
    
    int len= hist.length;
    //compute maxLeft
    for(int i=0; i< hist.length;i++)
    {
        maxLeft[i] = (i==0?hist[i] :Math.max(maxLeft[i-1],hist[i])); // i=0 is the base case. here maxLeft[i]=hist[i]
    }
    
    //compute maxRight.-- fill array from right.
    for(int i=len-1;i>=0;i--)
    {
        maxRight[i]=(i==len-1? hist[i]: Math.max(maxRight[i+1],hist[i]));// i=len-1 is the base case. here maxRight[i]=hist[i]
    }
    //now to calculate amount of water stored
    int volume=0;
    for(int i=0;i<len-1;i++)
    {
        volume +=Math.min(maxRight[i],maxLeft[i])-hist[i]
    }
    
    return volume;
}