Given an array of positive integers representing 2D bar heights, design an algorithm that can compute the total volume of water that could be held in all lakes on such an island given an array of the heights of the bars. Assume an elevation map where the width of each bar is 1 unit.
Example Given Array of heights [1,3,2,4,1,3,1,4,5,2,2,1,4,2], return 15 (3 bodies of water with volumes of 1,7,7 yields total volume of 15).
Input: [1,3,2,4,1,3,1,4,5,2,2,1,4,2]
Output: 15
My Approach:
 Iterate the Array of heights.
 Find maximumBefore(maximum height before the current height)
 Find maximumAfter(maximum height after the current height)

If
current is greater than maximumBefore or maximumAfter, update maximumBefore and continue,else
the volume at current height will be(minimum of maximumAfter, maximumBefore)  height
.
CODE:
var a = [1,3,2,4,1,3,1,4,5,2,2,1,4,2];
function getVolume (arr) {
let maxBefore = 0;
let answer = 0;
let maxAfter = 2;
for(var i = 1; i < arr.length1; i++){
if(arr[i] >= arr[maxBefore]) {
maxBefore = i;
continue;
}
if(i >= maxAfter){
let max = i+1;
for(var innerIndex =i+1; innerIndex< arr.length; innerIndex +=1) {
if(arr[max]<=arr[innerIndex]) {
max= innerIndex;
}
}
maxAfter = max;
}
if(arr[i] < arr[maxBefore] && arr[i] < arr[maxAfter]) {
answer += Math.min(arr[maxBefore], arr[maxAfter])arr[i];
}
}
return answer;
}
let sol = getVolume(a);
console.log('volume of lakes: ',sol); //volume of lakes: 15
Let's discuss your approach in the discussion box or you can hit me up at aastha.talwaria29@gmail.com.
Thanks for reading.
Top comments (0)