Mathematical explanation of Leetcode question: Container With Most Water

user_13814528 0
Viewed 144

I was working on a medium level leetcode question 11. Container With Most Water. Besides the brute force solution with O(n^2), there is an optimal solution with complexity of O(n) by using two pointers from left and right side of the container. I am a little bit confused why this "two pointers" method must include the optimal solution. Does anyone know how to prove the correctness of this algorithm mathematically? This is an algorithm that I don't know of. Thank you!

The original question is:

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container.

A brutal solution for this question is(O(n^2)):

    def maxArea(self, height: List[int]) -> int:
        length = len(height)
        volumn = 0
        #calculate all possible combinations, and compare one by one:
        for position1 in range(0,length):
            for position2 in range (position1 + 1, length):
                if min(height[position1],height[position2])*(position2 - position1) >=volumn:
                    volumn = min(height[position1],height[position2])*(position2 - position1)
                else:
                    volumn = volumn
        return volumn

Optimal solution approach, The code I wrote is like this(O(n)):

    def maxArea(self, height: List[int]) -> int:
        pointerOne, pointerTwo = 0, len(height)-1
        maxVolumn = 0
        #Move left or right pointer one step for whichever is smaller
        while pointerOne != pointerTwo:
            if height[pointerOne] <= height[pointerTwo]:
                maxVolumn = max(height[pointerOne]*(pointerTwo - pointerOne), maxVolumn)
                pointerOne += 1
            else:
                maxVolumn = max(height[pointerTwo]*(pointerTwo - pointerOne), maxVolumn)
                pointerTwo -= 1
        return maxVolumn

Does anyone know why this "two pointers" method can find the optimal solution? Thanks!

arrays algorithm python
2 Answers

Based on my understanding the idea is roughly:

  • Staring from widest bars (i.e. first and last bar) and then narrowing width to find potentially better pair(s).

Steps:

  1. We need to have ability to loop over all 'potential' candidates (the candidates better than what we have on hand rather than all candidates as you did in brutal solution) thus starting from outside bars and no inner pairs will be missed.

  2. If an inner bar pair does exist, it means the height is higher than bars we have on hand, so you should not just #Move left or right pointer one step but #Move left or right pointer to next taller bar .

  3. Why #Move left or right pointer whichever is smaller? Because the smaller bar doesn't fulfill the 'potential' of the taller bar.

The core idea behind the steps is: starting from somewhere that captures optimal solution inside (step 1), then by each step you are reaching to a better solution than what you have on hand (step 2 and 3), and finally you will reach to the optimal solution.

One question left for you think about: what makes sure the optimal solution is not missed when you executing steps above? :)

user_188607520

An informal proof could go something like this: imagine we are at some position in the iteration before reaching the optimal pair:


                           |
                           |
   |~~~~~~~~~~~~~~~~~~~~~~~|
   |~~~~~~~~~~~~~~~~~~~~~~~|
   |~~~~~~~~~~~~~~~~~~~~~~~|
   |~~~~~~~~~~~~~~~~~~~~~~~|
   ^                       ^
   A                       B

Now lets fix A (the smaller vertical line) and consider all of the choices left of B that we could pair with it. Clearly all of them yield a container with a smaller amount of water than we have currently between A and B.

Since we have stated that we have yet to reach the optimal solution, clearly A cannot be one of the lines contributing to it. Therefore, we move its pointer.

Q.E.D.

user_20347870
Related