Leetcode 11. Container With Most Water

Problem

Leetcode 11 - Container With Most Water

Example:

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.

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

Approach

We can use two pointer to solve this problem

We can get the area using $area = (right-left) * min(height[left], height[right])$ we want to use the min, as if we use the bigger value, the water will overflow.

Using the formula we can retrieve the max Area.

We can also move the pointer to either left or right by whichever is smaller. Meaning that if height[left] < height[right] then we move left pointer by 1, else we move right pointer by 1

Visualization of the Approach:

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
left, right = 0, 8
height[left], height[right] = 1, 7
area = (8-0) * min(1,7) = 8
maxArea = 8
Since left is smaller move left pointer

left, right = 1, 8
height[left], height[right] = 8, 7
area = (8-1) * min(8,7) = 49
maxArea = 49
Since right is smaller move right poitner

left, right = 1, 7
height[left], height[right] = 8, 3
area = (7-1) * min(8,3) = 18
maxArea = 49
Since right is smaller move right poitner

left, right = 1, 6
height[left], height[right] = 8, 8
area = (6-1) * min(8,8) = 40
maxArea = 49
Since they're equal we can move any poitner

left, right = 1, 5
height[left], height[right] = 8, 4
area = (5-1) * min(8,4) = 16
maxArea = 49
Since right is smaller move right poitner

left, right = 1, 4
height[left], height[right] = 8, 5
area = (4-1) * min(8,5) = 15
maxArea = 49
Since right is smaller move right poitner

left, right = 1, 3
height[left], height[right] = 8, 2
area = (3-1) * min(8,2) = 4
maxArea = 49
Since right is smaller move right poitner

left, right = 1, 2
height[left], height[right] = 8, 6
area = (2-1) * min(8,6) = 6
maxArea = 49
Since right is smaller move right poitner

Since left == right we can return maxArea

maxArea = 49

Here is the Python code for the solution:

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

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

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return res    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$