Quest from twitter interview

waterfill

var calculate = function( arr ){ // one cycle solution
    var minMax, 
        sum = 0, 
        fullSum = 0,
        el, 
        maxMax,
        i, _i = arr.length - 1;
        
    minMax = arr[0]; // first item is the current left max
    maxMax = arr[_i]; // last item is the current right max
    
    for( i = 0; i <= _i; i++ ){
        el = arr[ i ];
        if( minMax < el ){ // if the wall is getting higher
            sum += ( el - minMax ) * i; //add rectangular currentHeight-lastHeight x distanceFromStart
            fullSum += ( el - minMax ) * i; //add such rectangular to the whole avaliable free space
            minMax = el;
        }else{ // if we are getting down
            fullSum += minMax - el; // add down delta to the whole avaliable free space sum
        }
        el = arr[ _i - i ];
        if( maxMax < el ){ // same from the right side
            sum += ( el - maxMax ) * i; 
            maxMax = el;
        }
    }
    return fullSum - sum; // here we get whole avaliable space and reversed space that would be filled with water
};

// testing
[
    [[0,0,0,10,0,0,0,0,0],0],
    [[0,1,0,10,0,0,0,0,0],1],
    [[1,0,1], 1],
    [[5,0,5], 5],
    [[0,1,0,1,0], 1],
    [[1,0,1,0,1,0,1,0], 3],
    [[1,0,1,0], 1],
    [[1,0,1,2,0,2], 3],
    [[2,5,1,2,3,4,7,7,6], 10],
    [[5,1,0,1],1],                 //# thanks https://news.ycombinator.com/item?id=6640085
    [[2,5,1,2,3,4,7,7,6,3,5], 12] //# thanks https://news.ycombinator.com/item?id=6640105
].forEach(function( el ){
    if( calculate( el[0] ) !== el[1] ) throw( el );
});

You can calculate fullSum by subtraction (sum of all elements) from (full graph area).

fullSum = (arr.length * minMax) - (sum of all elements);

You are quite right, also I can stop calculating it and just change sum += to sum -= and replace fullSum += to sum -=. But I like this solution geometrically, I draw it first on paper and it looks logical and cool, I want to make a gif with an animation of process, but for me it's easier to make it on canvas, but I haven't got skill to convert it to gif :(

Not sure if I understand you. You can't replace sum += to sum -= cause you don't know sum at the very begining, so you need to pass all elements at least once to calculate it (and find out minMax value). Please check my fork. I'm not very experienced with JS, but hope solution is clear.

I really liked your idea to calculate 'air' rectangles. In my tests it showed better speed (~10-20%) then solution in original habrahabr topic, especially with big arrays.

As for GIF - have you checked the following link?
http://stackoverflow.com/questions/10486084/generate-animated-gif-with-html5-canvas