LeetCode 42 - Trapping Rain Water
Sometimes, I like to write my own editorial for (algorithm) problems I solved. I write it on my CP Log (Competitive Programming Log — it is just a google docs file where I dump interesting problems I found and my thoughts). If you are doing competitive programming or preparing for technical interview, you should try writing your own editorial for problems you solved. Penning down your ideas and thoughts helps you consolidate your knowledge and trains you to communicate your ideas more effectively.
So, in this blog post I am going to talk about LeetCode problem 42 — Trapping Rain Water. You can access the problem here: https://leetcode.com/problems/trapping-rain-water/
Problem StatementYour are given the elevation of some terrain and asked to compute the amount of water trapped after raining. The elevation is given as an array of non-negative integers. The amount of water is calculated in number of blocks.
The problem does not specify the size of the given array. So, we have to strive to produce the fastest possible solution. Since reading the array itself is about O(n), the fastest possible solution will be bottlenecked by input process, and thus also run in O(n).
We know that water will only be trapped in bowl-like structures. So, we only need to find these bowl-like structures and calculate the amount of water each bowl holds, right? Maybe, we can go from left to right and look at the height of each point, if it goes down then up, it must be a bowl. After that, we can calculate the height of water in each bowl by taking the minimum elevation height of the two edges of the respective bowl. Finally, we sum all the water in every bowls and get the answer. This solution runs in O(n).
Yes, this solution works if we are only calculating amount of water in simple bowl-like structures. The problem do not guarantee such condition, therefore, we need to be aware of more complex shape. Consider this, what happens if there are nested bowls (there are multiple bowls inside a bowl)? Or if there are weird bowl shapes? Or nested weird bowl shapes?
Let’s try another way. Imagine we are walking on the terrain from left to right. If the terrain is going up, we know that no water will trapped since the water will just flow down to where we come from (left edge). If the terrain is going down, we can assume two conditions:
- the terrain is going down forever and no water will be trapped.
- the terrain is going up at some point later and there will be water trapped.
How do we know that the terrain is going up at some point later without actually checking the elevation of multiple points ahead (this solution may work albeit running slower with O(n²) complexity)? Yes, you are right. It would be nice if there is someone else (our friend) on the other side telling us the elevation of the terrain so we can infer whether the terrain is going up or down forever. If our friend is on higher ground than our current position, we can be sure that the terrain is going up later (at the point where our friend is currently standing). Therefore, any terrain with lower elevation than our current position and is between our friend and us will definitely trap water. The amount of water trapped in a point will be the difference between the elevation of our current position and the elevation of the respective point.
If our friend is on lower ground, then we cannot infer anything (maybe there is a large mountain in between us or maybe the whole terrain is just going down hill from our place to our friend’s place).
Wait a moment … What if when our friend is on a lower ground, instead of we infer from her position, she can infer from our position and calculate the amount of water on the other side of the terrain for us? Boom! It is a great idea.
We can use two pointers: one pointing at the start (left side) of the terrain and the other pointing at the end (right side) of the terrain. The left pointer will move to the right and calculate amount of water trapped as it goes to the right, and the right pointer will do the same things moving towards the left.
Time complexity: O(n).
Space complexity: O(n).
Space complexity: O(n).
Originally published at vincentalfred.wordpress.com on January 27, 2019.
Also published at medium.com/@vincentalfred on January 27, 2019.