Container With Most Water (Leetcode #11)

11. 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 i<sup>th</sup> 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 <= 10<sup>5</sup>

• 0 <= height[i] <= 10<sup>4</sup>

Answer:

Approach 1 (Brute Force)

Using brute force method we can check every combination of the height to see which combination gives us the maximum volume but the time complexity of this code would be O(N^2) since for every height we would have to check for every height in the list.

Approach 2 (Two Pointers)

1. Create the two pointer at each end of the list

2. The formula for finding the volume of water at any given moment is
   (r-l) * min(height[l], height[r])

3. We keep checking if the volume is greater than our current max, if so we update the answer otherwise we keep going

4. To get the maximum volume at all time we should only shift in the pointer with less height since the width will always decrease by one and the height would be the maximum between left and right. If we move the taller one we would always end up with less height, hence it will not provide optimal answer

5. If we have equal height we should be able to move either the left or the right pointer since the algorithms should take care of the rest

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l = 0 
        r = len(height) - 1
        volume = 0
        while l < r:
            temp = (r-l)*min(height[l], height[r])
            volume = max(volume, temp)
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return volume

Time Complexity:

Since we are using the two pointer method and looping through the code ounce, the time complexity is O(n)

Space Complexity:

The space complexity is O(1) since we are only creating extra space to store the answer hence it doesn't scale with increase n