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.
Your 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.
This is the story of my Final Year Project (FYP). The goal of this blog post is to share our thought process, get feedback from the readers and hopefully inspire many of you. Introduction I'm a final year computer engineering student. As final year students, we are required to produce a capstone project. I am taking this opportunity to brush up my skills and improve my resume . Idea Together with my FYP-mate, Chandra , we are going to make hardware access control system. Most likely, our project is going to be implemented in our university's Hardware Lab. We are going to design system that: Controls who is able to use hardware (power tools i.e. drill press, grinder, etc.). For instance, only students who have gone through training for a particular hardware will be granted the access. Allows the lab to get usage data which may assist in hardware maintenance and/or upgrade. The system consists of two main components: a controller device for each hardware and ...
Many friends of mine have their own blogs. It's pretty cool to share your thoughts with the world. So I decided to create one for myself. When registering for the domain, it said vincentalfred.wordpress.com has already been used. I looked it up and ... damn I had totally forgotten. It is mine. HAHA. So many things had happened since my last post . I guess, I was preparing for A Level at that time (I took A Level at 2014). Higher 2 (H2) Level Art was one of my subjects, and I dreamed of becoming an animator or a visual designer. But now, I am studying Computer Engineering at Binus University. Maybe, in the future, I will write about my journey transitioning from arts to engineering. In this "new" blog, I am going to write about my projects and my interests, and maybe share my artworks if I start drawing again. I am reposting this (previously posted on my Wordpress ) as Blogger gives me a more customizable and versatile blogging experience. Also because I just bough...
Comments
Post a Comment