Skip to content

Instantly share code, notes, and snippets.

@bdw
Created December 26, 2013 16:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bdw/8135979 to your computer and use it in GitHub Desktop.
Save bdw/8135979 to your computer and use it in GitHub Desktop.
function to calculate volume contained in the 'pools' in a two-dimensional array.
function calculateVolume(heights) {
var left = 0, right = 1, volume = 0;
while (right < heights.length) {
var level = heights[left];
if (heights[right] <= level) {
// tag the 'left cursor' along
left = right;
right = right + 1;
} else {
// walk to the left
while (left >= 0 && heights[left] <= level) {
left -= 1;
}
// over the edge, so no volume to be filled
if (left < 0) {
left = right;
right += 1;
} else {
// add the volume to the total
var distance = right - left;
var peak = Math.min(heights[left], heights[right]);
volume += (distance - 1) * (peak - level);
}
}
}
return volume;
}
document.write(calculateVolume([3,2,1,0,4]));
document.write("<br />");
document.write(calculateVolume([1,3,4,2,0,1,3,2,5,3]));
document.write("<br />");
document.write(calculateVolume([4,3,2,1,0,3]));
@bdw
Copy link
Author

bdw commented Feb 14, 2014

I think there should be a divide-and-conquer strategy to do this. But I'm not sure how.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment