This content originally appeared on DEV Community and was authored by Santiago Salazar Pavajeau
This is a fast and simple solution for the trapping rainwater problem. We just use two pointers, for the start and end of the list. Then keep track of the highest columns so far from the start sMax and the end eMax.
sMax = Math.max(sMax, height[str])
eMax = Math.max(eMax, height[end])
Then, the pointer that is higher stays in its position, and the other moves.
if(sMax < eMax){ // move start pointer
water+= sMax - height[str++]
// highest left yet, minus current
}else{ // move end pointer
water+= eMax - height[end--]
// highest right yet, minus current
}
This allows calculating the water by subtracting the current height from the max height.
// [0,1,0,2,1,0,1,3,2,1,2,1] result: 6
// [4,2,0,3,2,5] result : 9
// calculate the water between the columns of height -> height[current]
const trapRainWater = (height) => {
let str = 0,
end = height.length - 1,
water = 0,
sMax = 0,
eMax = 0;
while(str<=end){
sMax = Math.max(sMax, height[str])
eMax = Math.max(eMax, height[end])
if(sMax < eMax){ // move start pointer
water+= sMax - height[str++]
// highest left yet, minus current
}else{ // move end pointer
water+= eMax - height[end--]
// highest right yet, minus current
}
}
return water
}
Feel more than welcome to reach out with any ideas/comments at Linkedin or Twitter, and check out my portfolio!.
This content originally appeared on DEV Community and was authored by Santiago Salazar Pavajeau
Santiago Salazar Pavajeau | Sciencx (2021-04-09T10:24:23+00:00) Simple trapping rainwater. Retrieved from https://www.scien.cx/2021/04/09/simple-trapping-rainwater/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.