The water is *just* fine! And what water is that, you might be asking? Why, the Flood Depth exercise on Codility, of course! The exercise, designed to test your ability to manipulate arrays efficiently, proved to be a fascinating journey into algorithmic thinking and problem-solving.
At first glance, the Flood Depth problem seems very… not so very straightforward. We are given an array representing the heights of terrain blocks with the task of calculating the maximum depth of water that could be trapped between the blocks when it rains. It sounds simple, yet the devil lays silently (or not so silently) in the details.
The essence of the exercise lies in identifying the locations where water could be trapped. To do this, I had to analyze the array and discern the boundaries of each potential water basin by traversing from left to right and then back from right to left. How well-versed are you in traversing arrays?
My first approach was a naive one – iterate through each block to the right and then iterate through each block to the left. This involved two separate for-loops (and two separate arrays- a big no-no) that led to a time complexity that most definitely could be improved. And while it may have lacked the efficiency that is often crucial in real-world applications, I’m proud to say that it was pretty readable 😉
As I delved deeper into the problem, I realized the key was to take the minimums of left and right, which are the points where water could start accumulating and subtract that our original array. Not so deep after all, lol! Now, could I employ a stack-based approach? Sure, maybe- as the stack would allow me to keep track of the ascending order of terrain heights. However- for now, I am appending going to the right and then inserting going to the left.
Overall, the elegance of this algorithm lies in its efficiency. Nevertheless, the Flood Depth exercise on Codility wasn’t just about finding an efficient solution though, as it’s prompted me to consider at least one edge case that might break my implementation. But what if there were multiple local minima close to each other? What if the terrain had a single peak with no depressions?
I’m not quite at the place of tweaking my algorithm as of yet because…. I submitted my program into Codility and got a fairly good score (at least to me! And I am stoked about it!) for the very first submission (if you want to know what that is- be sure to watch my YouTube video premiering on Thursday at 8:15PM EST!).
Ultimately, I was able to break it down into five “gears” – iterating to the right, iterating to the left, creating an array of minimums between the left and right, creating an array of “results” and then returning the “max” of that *result*.
As always, there are so many ways you can solve this- the program I wrote (in my video) with my five “gears” is how I chose to do mine. How would you write your program?
_________________________
Thanks for reading! Don’t forget to set an alarm for Thursday at 8:15pm!! Where I break down the whooooole problem and show the results of my test… be there or be square 🙂
Click HERE to visit my channel 3>