11. Container With Most Water

Description:

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

 

'''
[1] brute force - Time Limit Exceeded)

code::
max_water=-1
for i in range(len(height)):
    for j in range(i,len(height)):
        max_water=max(max_water,min(height[i],height[j])*(j-i))
return max_water


complexity::
- T/C: O(n^2)
- S/C: O(1)
'''

'''
[2] two pointer and greedy)

code::
left=0
right=len(height)-1
max_water=-1

while left<right:
    max_water=max(max_water, min(height[left],height[right])*(right-left))
    
    if height[left]>=height[right]:
        right-=1
    else:
        left+=1
        
return max_water

complexity::
- T/C: O(n)
- S/C: O(1)
'''

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left=0
        right=len(height)-1
        max_water=-1

        while left<right:
            max_water=max(max_water, min(height[left],height[right])*(right-left))

            if height[left]>=height[right]:
                right-=1
            else:
                left+=1

        return max_water