Simple and clear proof/explanation


  • 99

    I've seen some "proofs" for the common O(n) solution, but I found them very confusing and lacking. Some even didn't explain anything but just used lots of variables and equations and were like "Tada! See?". I think mine makes more sense:

    Idea / Proof:

    1. The widest container (using first and last line) is a good candidate, because of its width. Its water level is the height of the smaller one of first and last line.
    2. All other containers are less wide and thus would need a higher water level in order to hold more water.
    3. The smaller one of first and last line doesn't support a higher water level and can thus be safely removed from further consideration.

    Implementation: (Python)

    class Solution:
        def maxArea(self, height):
            i, j = 0, len(height) - 1
            water = 0
            while i < j:
                water = max(water, (j - i) * min(height[i], height[j]))
                if height[i] < height[j]:
                    i += 1
                else:
                    j -= 1
            return water
    

    Further explanation:

    Variables i and j define the container under consideration. We initialize them to first and last line, meaning the widest container. Variable water will keep track of the highest amount of water we managed so far. We compute j - i, the width of the current container, and min(height[i], height[j]), the water level that this container can support. Multiply them to get how much water this container can hold, and update water accordingly. Next remove the smaller one of the two lines from consideration, as justified above in "Idea / Proof". Continue until there is nothing left to consider, then return the result.


  • 0
    D

    "because of its width. Its water level is the height of the smaller one of first and last line."

    Q: Why the height of water level is not the shortest line within (first, last) ? (According to Cask Effect


  • 0

    I don't know the "Cask Effect" and Google only tells me that it has to do with aging whiskey :-)

    But the shortest line within is irrelevant, as we're supposed to "Find two lines, which together with x-axis forms a container...". Not together with all lines within. Just the two lines and the x-axis form the container.


  • 0
    D

    It was my mis-spelling, which should be Leaking Bucket Effect :-D

    Thanks for your reply.


  • 0
    D

    Very clear explanation. Thanks a lot.
    BTW, since lines lower than the the minimum height can be ignored, we can keep moving forward without updating water. It should be faster.


  • 0

    Yeah, here I just focused on the idea and didn't care about speed. I actually wrote an "optimized" solution a few weeks later. Even the explanation there might be better, because it makes a lot of sense to move both ends to the next higher line.


  • 0
    K

    This explanation made way more sense than the others. Thanks!


  • 0
    G

    Thank you, your explain is very short but useful and clear. After your explain, I fully understand why we do not have to iterate all possibilities. I think it will be even more straightforward if codes are written in recursion although it maybe will be a little slower.


  • 0
    Z

    I was making the same mistake as you did here.


  • 0
    B

    OMG, I have seen so many different version of explanation but no one does a better job than you for me. This is an awesome and easy to understand


  • 0
    P

    Thanks, this makes sense but I'm not sure how I could come up with the intuition without reading the answer first. Guess some things just take eureka moments.


  • 0
    L

    @StefanPochmann I hope you have more posts with such explanation instead of just typing a "xxx-line code solution". This explanation is crystal clear.


  • 0
    M

    @StefanPochmann I don't understand why j -= 1 when height[i] == height[j]. It is possible that j and another line contain mosr water.


  • 0

    @monkeyysh No it's not possible.


  • 0
    M

    @StefanPochmann I see, thanks!


Log in to reply
 

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