{{ message }}

Instantly share code, notes, and snippets.

# Zibx/waterfill

Last active Dec 27, 2015
 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 ); });

### GreenSmile commented Oct 31, 2013

 You can calculate fullSum by subtraction (sum of all elements) from (full graph area). fullSum = (arr.length * minMax) - (sum of all elements);

### Zibx commented Oct 31, 2013

 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 :(

### GreenSmile commented Oct 31, 2013

 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