Two pointer solution to rainwater capture needs some explaining

Can someone guide me through this code block that uses the two pointer approach to solving the capturing rainwater problem? It does not make sense to me.

function efficientSolution(heights) {
  let totalWater = 0;
  let leftPointer = 0;
  let rightPointer = heights.length - 1;
  let leftBound = 0;
  let rightBound = 0;
  
  while (leftPointer < rightPointer) {
    if (heights[leftPointer] <= heights[rightPointer]) {
      leftBound = Math.max(heights[leftPointer], leftBound);
      totalWater += leftBound - heights[leftPointer];
      leftPointer++;
    } else {
      rightBound = Math.max(heights[rightPointer], rightBound);
      totalWater += rightBound - heights[rightPointer];
      rightPointer--;
    }
  }
  return totalWater;
}

const testArray = [4, 2, 1, 3, 0, 1, 2];
console.log(efficientSolution(testArray));

// Leave this so that we can test your code:
module.exports = efficientSolution;

this is the actual challenge: https://www.codecademy.com/paths/pass-the-technical-interview-with-javascript/tracks/javascript-interview-prep-and-algorithm-practice/modules/javascript-algorithm-practice/articles/capturing-rainwater-js

hi @system7514817679. Thanks for posting your question! Before potential helpers can assist you with this, we’ll need a bit more information from you. We need to know what you’ve already tried, that is to say––we need to understand your process! Can you walk us through what you’ve already tried, which part of the code is blocking you, and anything else as it relates to your process of thinking through this code?

Thanks! :slight_smile:

1 Like

There is already a solution to the problem. I have posted this above. The problem I have is understanding this code block. The solution was provided by CodeCademy in the Interview challenges. However that was not accompanied by an explanation. So I would very much like to know how and why it works the way it works? What was the logic thinking behind the conception of the code? Thanks!

Hi @system7514817679!

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.
image image

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.

5 Likes

:clap: bravo @didash, your post was well written and extremely insightful.

The one thing I would add that’s helped me understand how “reverse engineering” a solution works is to add in console.log() statements where I’m not sure what’s happening.

For instance, I first added a console.log() statement to see how much total water had accumulated at the start of the while loop.

while (leftPointer < rightPointer) {
    console.log("totalWater is", totalWater, "leftPointer is", leftPointer, "rightPointer is", rightPointer)
    // ... rest of the code
  }

Then I added more console.log() statements to get a sense of the pointers are being shifted, notably in the if and else blocks. This way I got to see how the pointers change and as a result, how totalWater accumulates.

Just wanted to add this tidbit in addition to your great response :slight_smile: Thanks!

4 Likes

Thanks peeps. I will have a go at it

1 Like

@system7514817679 Hopefully you got on okay … and didn’t get too rage-quitty… I would recommend a good YouTube session and you’ll see how the 'Cademy adapted their problem from what I believe was Twitter or Google interview question. I wasn’t really on board with the two pointer solution either… But then I spent some time and actually saw it was rephrased as a lower envelope problem which is the optimal solution to this… I don’t know if I self-brute forced the answer with all the research but I found this explanation useful.

https://www.thealgorists.com/Algo/TrappingRain