First of all, I would like you to try to get to the solution on your own. But if you are still having problems I can help and give you some hints of what is happening. To understand what is going behind the scenes in coding it is always useful to reverse engineer it. To do this try writing out, on a piece of paper or your computer (whatever works best for you), step by step what is going on with each line of the code.
It is always useful to use all the sources you have, like the article you shared in a post as it has images that will help you through the process.
Try answering the questions I wrote here. If you still find it too difficult and don’t understand why this happens, open the hints to figure it out.
Why is it more efficient?
To begin with, let’s try to get around to why changing the code if the naive solution works. So, as you must have figured out already, the naive solution has a lot of nested for loops. This will make the process take a long time to complete. We should always try to write the same code using just one loop if possible.
For example, to do this, the optimized solution used a while loop, where instead of iterating through all the elements of the array and then looking for the right and left bounds for that element. We are actually just looping once, but going from the extremes to the center. From the outside to the inside. (Not in every case it works like this, to understand why open the next hint)
Two pointer solutions are helpful when you are working with boundaries, limits, or ranges. As it will save a minimum or maximum piece of data that will work with multiple elements of an array. This way you will already have the element to work with instead of looking for it each time.
Why using an if...else conditional?
As I mentioned, we are iterating from outside to inside. But how to know if we should increase the left pointer or decrease the right pointer or with which element I should work with. Here is where the if…else condition is used for. We should check the information inside of the array to notice which one provides us the most information or has two or more possible ways to be interpreted.
In two pointers solution, we won’t be moving both pointers at the same time. We should only move the one we just worked with. In some cases, we won’t even move one of the pointers (this is actually the case of the array provided by the example), as the condition will sometimes be true (or false), for all the iterations.
In the rainwater example, we are checking which of the two elements found in the array that the pointers are referencing is smaller, as we will work with the small element because it is either a boundary or it will be containing water. In other words, the big element will always be a boundary, so there is no need to work with it as it won’t contain water.
How is it processing the data and selecting the boundaries?
As you can see in the code, both of the conditions are doing the same thing with the element but it is being compared with different variables. We already know why did it choose to work with the left or right pointer, but now we need to know what to do with this information.
In this example, we selected the smaller element as it can be a boundary or contain water. To recognize which is the case, we have to compare it with the previous boundary we worked with. If we are working with an element that comes from the left, we compare it with the left boundary, in the other case we compare it with the right boundary. If it is bigger than the previous boundary, this means the last one won’t be of use anymore, turning this element into the new boundary.
The next thing is to increase the total water. To do this we will just accumulate total water with the difference of the boundary and the element we are working with. (If we just saved the current boundary as this element there won’t be any difference, so no water will be increased).
If you are still having problems with a part reply to this post with your specific question. Also, if you found this post helpful in any way don’t forget to submit it as the solution to let others know that this topic has been resolved.