0011. Container with most water

Problem Category:: Two pointer methods, Greedy algorithms Neetcode Category:: Two Pointer

https://leetcode.com/problems/container-with-most-water/

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.

Optimal

Two pointer (greedy)

Have two pointers on each end, close in, checking if it’s a new maximum

• Each time, we make the locally optimal solution of changing the pointer that is of lower height, since altering the higher pointer has no difference, since the area is always limited by the lower pointer

Python solution

class Solution:
    def maxArea(self, height: List[int]) -> int:
        curr_max = 0
        l, r = 0, len(height) - 1
        while l < r:
            area = (r - l) * min(height[l], height[r])
            curr_max = max(curr_max, area)
            if height[l] >= height[r]:
                r -= 1
            else:
                l += 1
        return curr_max

• Time complexity: $O(n)$ - 1 traversal
• Space complexity: $O(1)$