Two pointer solution to rainwater capture needs some explaining

Web Development
1

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;
2

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

3

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
4

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!

5

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.

6 Likes
6

: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!

5 Likes
7

Thanks peeps. I will have a go at it

1 Like
8

@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

9

it its very frustrating trying to complete this problem with such a small codebox provided by codecademy

2 Likes
10

After thoroughful hand plotting, I came to the conclusion that the pseudocode for the optimized solution does not work. Please let me know if I got it wronkg (very likely):

Using the histogram proposed as the input:

// starting values
totalWater = 0
leftPointer = 0 
rightPointer = heights.length - 1
leftBound = 0
rightBound = 0

while leftPointer < rightPointer
  if the element at leftPointer <= the element at rightPointer // this is never gonna be true given the input and that the left pointer will never move forward (see end of this if block)
    if the element is larger than leftBound, set leftBound to the element
    add the difference between leftBound and the element at leftPointer to totalWater
    move leftPointer forward by one // Left pointer will never move
  else
    if the element is larger than rightBound, set rightBound to the element // Since starting value of rigthBound is 0, it won't move from here. rightBound will be equal to this first element from now on
    add the difference between rightBound and the element at rightPointer to totalWater // this is the only calulation that will happen through the lenght of heights.  
    move rightPointer back by one // this is the only pointer that will move. Since none of the elements at rightPointer will be greater or equal to leftPointer, the first if block of the algo will never run.

return totalWater // 2 + 3 +4 +1 + 3 + 2 =  Great Flood and Noah gathering his pets.
11

Answering to myself after checking the solution:

  • leftBound and rightBound are not indexes, but “containers” that save the heights of left and right bounds. So wen the pseudo code says set leftBound to the element, what it means is to assign the value of the element to leftBound.

Ok. This one may have been a victim of my poor but beautifully accented english. But then, right after the else, as the first element of the conditional if , we find the element. What element is this? By looking at the solution code, it is the element at rightPointer. Why then, in the first if, the syntax the element at leftPointer is used, but then in the if that follows the else we only read the element?

In most languages, english included, this is knwon as ellipsis. Therefore, gramatically, it is understood that, as long as there is not a explicit declaration such as the element at rightBound, all the elements following the element at leftPointer should be refering to, preciselly, the element at leftPointer, which is not the case.