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!.
Top comments (0)