Solving Trapping rain water problem — Leetcode
A friend recommended leetcode.com to me and I’ve been lovingly using it to pass my time, when I’m bored. I’ve been trying to solve problems in the language I love, javascript.
Recently, I came across a problem called, Trapping Rain water and below is my solution to it.
Also, my musings about other leetcode problems are here, and the complete solution to this problem is here.
The Problem:
(or jump to solution below)
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6The Solution:
Let’s start from the left (i=0) and let the height be h.
At i=0, h=0.
Let’s keep skipping calculation until the height is greater than 0, since that’s when the structure can start to hold water.
At i=1, h=1,
So, here let’s find a pillar that is taller than the current one. (keep marching towards the right, always)
Now, let’s find the area between these two pillars and store it in ‘areaTemp’.
The area that lies between the two pillars is (height of the smallest pillar) x (distance between the pillars).
We choose the height of the smallest pillar because that will constitute the height of the container formed by two pillars.
However, this would not be the exact area the water could take up. Consider the hollow below,
The area between two tallest pillar is occupied by two small pillars. So we need to subtract the heights of those pillars from the total area.
From the total area calculated previously, we now subratract the height of smaller pillars between the two tallest pillars.
This final area gives us the total area the water can cover.
The code is given below,
Now, the tallest pillar on the right is taken as the current pillar. This calculation of area is repeated until we reach the last pillar.
These intermediate areas are summed up to give us the total area the water can cover in the structure.
The full code is available, here.
Thanks for reading.
Let me know what you think about the solutions. If you have any questions, please feel free to drop a mail at divya261261@gmail.com
Do not forget to clap, if you liked the read. :)
