LC 11 - Container With Most Water

Question

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

Links

Question here and solution here

Solution

concept

We will use a greedy + two pointer method to calculate the maximum area. Basically we have l and r pointer that start at the beginning and end of the array and compute the area. We then move which ever lower bar towards the center and compute the area again. We will keep track the maximum area this way.

code

class Solution:
	"""
	two pointer solution
	"""
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        ans = 0

        while l < r:
            area = (r - l) * min(height[l], height[r])
            ans = max(ans, area)
            if height[l] >= height[r]:
                r -= 1
            else:
                l += 1
        
        return ans    

Complexity

time: $O(n)$
space: $O(1)$