The True Complete Proof of the Correctness of the Solution


  • 3
    L

    The other answers with explanations all prove that, starting from the edge, with the moving strategy ( i.e. move the pointer of the smaller value to the inner side ), the amount of water will increase sometime in the future.

    However, can the maximum value be reached? That's the key problem.

    Here is my proof of why the maximum value can be reached definitely.

    Given a1, a2, ..., an.

    First of all, let's assume that the optimal choice of the container with the most water is ( ai, aj ) ( i < j ). Then I just need to prove that there will definitely exist one situation where the left pointer is at ai while the right pointer is at aj.

    Then I will prove that a1, a2, ...and ai-1 are all smaller than aj. This proof is simple, because if ak >= aj and 1 <= k <= i-1, then the optimal choice would be ( ak, aj ), not ( ai, aj ).

    Symmetrically, aj+1, aj+2, ...and an are all smaller than ai.

    Finally, during the movement of the pointers, either ai or aj will be reached at first, so let's assume ai is reached before aj. Then because aj+1, aj+2, ...and an are all smaller than ai, so the right pointer will continue moving ( because the value it points to is smaller ) until it reaches aj. Now the left pointer is at ai and the right pointer is at aj.

    And if aj is reached before ai, the proof is also obvious.


  • 0
    L
    This post is deleted!

  • 0
    W

    Hi, I am confused by why you said that a1, a2, ...and ai-1 are all smaller than aj. I think we could only claim that a1, a2, ...and ai-1 are all smaller than ai. Could you explain a bit more? Thanks!


  • 0
    L

    Assume that there exists a number k which satisfies 1 <= k <= i-1 and ak >= aj, then the optimal choice would be (ak, aj) not (ai, aj), which is contradictory to our hypothesis that (ai, aj) is the optimal solution to this problem.


  • 0
    J

    Based on the true complete proof.


    Given a1, a2, ..., an.

    First of all, let's assume that the optimal choice of the container
    with the most water is ( ai, aj ) ( i < j ). Then I just need to prove
    that there will definitely exist one situation where the left pointer
    is at ai while the right pointer is at aj.

    Then I will prove that a1, a2, ...and ai-1 are all smaller than aj.
    This proof is simple, because if ak >= aj and 1 <= k <= i-1, then the
    optimal choice would be ( ak, aj ), not ( ai, aj ).

    Symmetrically, aj+1, aj+2, ...and an are all smaller than ai.

    Finally, during the movement of the pointers, either ai or aj will be
    reached at first, so let's assume ai is reached before aj. Then
    because aj+1, aj+2, ...and an are all smaller than ai, so the right
    pointer will continue moving ( because the value it points to is
    smaller ) until it reaches aj. Now the left pointer is at ai and the
    right pointer is at aj.

    And if aj is reached before ai, the proof is also obvious.

    Apparently, any (ak,am) such that 1<= k <= i-1, and j+1 <= m <=n, is not optimal,
    any (ak,am) such that i< k < m <j, is not optimal.
    When 1 <= k <= i-1 and i<= m <=j, there is f, j < f <= n, such that af > ak, and we have that (ak, af) is not optimal
    hence (ak,am) < (ak, af) < (ai,aj).

    I think the other cases are obvious.


Log in to reply
 

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