Skip to content

Instantly share code, notes, and snippets.

@Zibx Zibx/waterfill
Last active Dec 27, 2015

Embed
What would you like to do?
Quest from twitter interview
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

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link
Owner Author

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

This comment has been minimized.

Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.