Accepted solution in Python with O(n) time complexity


  • 0
    L

    start with left =0 and right = len(height)-1

    if the left height is lower, it determine the height of the water. by increase left by one we may increase the capacity. However if the height of the left boundary decrease, for sure, the capacity would decrease.

    Do the similar operation for the case if the right boundary is the bottleneck.

    class Solution:
        # @return an integer
        def maxArea(self, height):
            left,right=0,len(height)-1
            maxi=(right-left)*min(height[left],height[right])
            while left+1<right:
                if height[left]>height[right]:
                    right-=1
                    if height[right]>height[right+1]:
                        maxi=max(maxi,(right-left)*min(height[left],height[right]))
                else:
                    left+=1
                    if height[left]>height[left-1]:
                        maxi=max(maxi,(right-left)*min(height[left],height[right]))
            return maxi

Log in to reply
 

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