Advertisement
DarkSoul144

O(n) solution for "Water in a Bar Graph" Problem

Jun 24th, 2018
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // O(n) solution for "Water in a Bar Graph" Problem.
  2. var bar = [10,2,10, 1, 3, 7];
  3. var water = 0;
  4. var maxIndex = 0;
  5. for (var i = 1; i < bar.length - 1; i++) {
  6.     if (bar[i] < bar[maxIndex]) {
  7.     water += bar[maxIndex] - bar[i];
  8.   } else {
  9.     maxIndex = i;
  10.   }
  11. }
  12. if (bar[bar.length - 1] < bar[maxIndex]) {
  13.     water -= (bar.length - 2 - maxIndex) * Math.abs(bar[bar.length - 1] - bar[maxIndex]);
  14. }
  15.  
  16. document.write(water);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement