Problem Description

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]).

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.

Example 1:

36.ValidSudoku.png

  • Input: height = [1,8,6,2,5,4,8,3,7]
  • Output: 49
  • Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

  • Input: height = [1,1]
  • Output: 1

My Idea

The idea here is to utilize two pointers starting at opposite ends of the heights array. We calculate the area of the resulting container and move the pointer from the lower height inwards in search of a bigger container. We do this until the pointers meet and in the end return the maximal possible Area => the container with the most water.

My solution

# Time complexity: O(n)
def maxArea(height: list[int]) -> int:
    mA=0
    s=0
    e=len(height)-1
    while(s<e):
        tA=min(height[s],height[e])*(e-s)
        mA=max(mA,tA)
        if height[s]<height[e]:
            s+=1
        else:
            e-=1
    return mA