DEV Community

loading...

Simple trapping rainwater

santispavajeau profile image Santiago Salazar Pavajeau ・1 min read

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])
Enter fullscreen mode Exit fullscreen mode

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
        }
Enter fullscreen mode Exit fullscreen mode

This allows calculating the water by subtracting the current height from the max height.

by Inge Maria in Unsplash


// [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
}

Enter fullscreen mode Exit fullscreen mode

Feel more than welcome to reach out with any ideas/comments at Linkedin or Twitter, and check out my portfolio!.

Discussion (0)

pic
Editor guide