Container With the Most Water

Patrick Leaton
Published: June 13, 2021, 5:17 p.m.
Problem Description

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

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

Example 3:

Input: height = [4,3,2,1,4]
Output: 16

Example 4:

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

 

Constraints:

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

 

The description was taken from https://leetcode.com/problems/container-with-most-water/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def maxArea(self, height: List[int]) -> int:
        most_water, left, right = float('-inf'), 0, len(height) - 1
 
        while left < right:
            water = (right-left) * min(height[left], height[right])
            most_water = max(most_water, water)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
 
        return most_water

Problem Explanation

This problem has to do with finding the right combination of left and right sides that can contain the most water possible.

A brute force approach would be to try every possible combination, but that would be far too slow.  We don't need to try every possible combination, only the combinations that can be greater than the current container we have.

The container that will hold the most water may be the widest, or it may be the tallest since a two-dimensional area is calculated by multiplying the width and the height.

What we can do is test the widest container first.  The width of this container would be the distance from the first and last elements within the array.

Then, we can continue to test for the tallest container.  What we will do is compare the left and right sides of the container, and whichever side is smaller, we will remove to try and get a taller one.

Whenever our sides overlap, that means we have searched the entire space and will return the container we found that can hold the most water.

Let's initialize our running most_water maximum, then our left and right pointers to the first and last indices of the input array.

        most_water, left, right = float('-inf'), 0, len(height) - 1

 

Then, while the left side and the right side of the container haven't overlapped, we will continue to try and get the container that can hold the most water.

        while left < right:

 

The amount of water the current container can hold will be the distance between the two sides, the width, and the minimum of the two heights, the length.  The reason for this is we can't fill a container past the shortest of the two sides without water flowing out over the smaller side.

            water = (right-left) * min(height[left], height[right])

 

We'll test the current amount of water this container can hold versus the maximum we have saved, and if it is greater, we will save the current water potential as the most water potential so far.

            most_water = max(most_water, water)

 

Now let's try and get taller sides.  

We'll do this by scrapping the smallest side and moving its pointer inward.

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

 

If the sides are the same, it doesn't really matter which one we pick to move because a container can only hold up until the length of the shortest side, as mentioned previously.  We aren't going to miss a potential, better container by scrapping the wrong side if they're equal because we can only get greater height combinations by removing the smaller ones.  We are moving the pointers inward from the greatest width, so we will inevitably cross the greatest height combination eventually.  Let's not forget the width also plays an important role in determining the most water potential so this isn't just about looking at the greatest two heights.

Once we have found the container that can hold the most water, we will return the most water it could hold.

        return most_water