An Easy Graphical Proof of the O(n) Two Pointer Solution


  • 0

    I struggled to be fully convinced that the two pointer solution (Editorial Solution) works; I need some proof. After some thinking I found the following graphical explanation pretty intuitive to me:

    The algorithm is actually determining the Water Level Line after all possible spaces are filled with water. Something like finding the skyline.

    Imagine the following bucket,

                       |
              |        |
              |  |     |
        |     |  |     |  |
     |  |  |  |  |     |  |
     |__|__|__|__|__|__|__|
    

    Now let‘s imagine that there is a pipeline under each bin, these pipelines pipe water into their bins at the same rate. You can imagine a constantly increasing Water Level Line and it will eventually stabilize when all possible spaces are filled and the water will flow out of the bucket since the walls cannot hold it. The final Water Level Line (denoted by ...) will be:

               ........|
              |        |
         .....|  |     |..
      ..|     |  |     |  |
     |  |  |  |  |     |  |
     |__|__|__|__|__|__|__|
       ^  ^  ^  ^  ^  ^  ^
       ^  ^  ^  ^  ^  ^  ^
    

    The two pointer algorithm will help us find it, and here is how:

    Step 1. The first piece of the Water Level Line that stabilizes must happens at the boundary (the leftmost or the rightmost point, i.e, wall 0 and wall 7). There will be NO inner pieces of Water Level Line that are below this line, why? Because if there is one, then the water will just flow into that lower region and fill that space. The height of the Water Level Line equals the smaller of the heights of the two end points (0 and 7). The current Water Level Line is as follows: (,,, denotes temporary Water Level Line)

                       |
              |        |
              |  |     |
      ,,|,,,,,|,,|,,,,,|,,|
     |  |  |  |  |     |  |
     |__|__|__|__|__|__|__|
     0  1  2  3  4  5  6  7
    

    Step 2. Now we continue piping water into the bucket (continue raising the Water Level Line). What is the next stabilized piece of Water Level Line? Imagine that the Water Level Line increases until the next level is found:

                       |
              |        |
         ,,,,,|,,|,,,,,|,,
      ..|     |  |     |  |
     |  |  |  |  |     |  |
     |__|__|__|__|__|__|__|
     0  1  2  3  4  5  6  7
    

    To find this new Water Level Line, you try changing wall 0 to wall 1 hoping that change the previous lower wall may increase the Water Level Line and it works!

    Step 3. We continue to raise the Water Level Line. 1 and 7 have same heights so we simultaneously change 1 to 2 and change 7 to 6. Changing only one of them will never give you a higher Water Level Line since the new Water Level Line will always bounded by the other one. Unfortunately, 2 and 6 gives a even lower Water Level Line so we need to change 2 to 3 in order to get a higher one; and this time we do get a higher one, as follows:

               ,,,,,,,,|
              |        |
         .....|  |     |..
      ..|     |  |     |  |
     |  |  |  |  |     |  |
     |__|__|__|__|__|__|__|
     0  1  2  3  4  5  6  7
    

    Step 4. We still hope to further increase Water Level Line so we try changing 3 to 4, however it does not work. So we try again to change 4 to 5, which does not work either. We have tried all potential walls so now we have drew the final Water Level Line:

               ........|
              |        |
         .....|  |     |..
      ..|     |  |     |  |
     |  |  |  |  |     |  |
     |__|__|__|__|__|__|__|
     0  1  2  3  4  5  6  7
    

    In the above procedure, we always keep track of the area under each newly found piece of Water Level Line and the largest area is the answer we are looking for. As you can see, the above procedure is exactly the two pointer solution (Editorial Solution). And the proof is simply done by basic physic laws, i.e., that water will flow into lower region and fill that space, and the bucket theory, i.e., the Water Level Line is determined by the lower wall.

    I hope this graphical explanation helps :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.