Day 18: Container With Most Water: Two Pointers - leetcode - Python3

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith 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:

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

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

SOLUTION:

class Solution:

    def maxArea(self, height: List[int]) -> int:

        maxA: int=0

        l: int=0

        r: int=len(height)-1

        while l < r:

            h: int=min(height[l], height[r])

            maxA = max(maxA, (h * (r-l)))

            if h==height[l]:

                l =l+1

            else:

                r =r-1

        return maxA            

               

Time Complexity: O(n)

Space Complexity:O(1)

How it works:

This code uses a two-pointer approach to find the container with the maximum area.

1. Initialize maxA to 0, which will hold the maximum area.
2. Initialize l to 0, representing the left pointer, and r to len(height) - 1, representing the right pointer.
3. Enter a while loop, which runs as long as l is less than r.
4. Calculate the height h as the minimum value between height[l] and height[r].
5. Calculate the area h * (r - l) and update maxA if this area is greater than the current maximum area.
6. Move the pointers inward based on the height comparison.
   • If h is equal to height[l], increment l by 1.
   • If h is equal to height[r], decrement r by 1.
7. After the while loop ends, return the maximum area maxA.