[Python] Mathematical explanation of Leetcode question: Container With Most Water

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). 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!

Continue reading...