In today’s post, we’ll discuss the Container with Most Water problem taken from Leetcode 11.
Table of Contents
Container With Most Water
For this challenge, you are given a list of non-negative numbers. Each number in the list represents the height of vertical bars in a container.
For instance, if we have the list [2, 1, 10, 2, 5, 4, 8, 3, 7], the numbers represent the height of vertical bars shown below:
Your task is to determine which two bars, when selected to be the sides of the container, form a container that contains the most water. You need to return the area formed by those two bars and the horizontal axis. The width of the bars is considered to be negligible and all bars are spaced one unit apart.
In the example above, you should return the value 42.
This is because the greatest area occurs when the third and last bars represent the sides of the container. Since the shorter bar has a height of 7 and the two bars are 6 units apart, the area is 7 x 6 = 42.
Suggested Approach
Approach 1 – Using Brute Force
The most intuitive approach to solving this problem is to consider all possible combinations of the two bars.
For instance, we can consider pairing the first bar with the second bar, or the first bar with the third bar, or the first bar with the fourth bar and so on. We can then compare the area formed by each combination and return the greatest area.
However, this approach is too slow and has a time complexity of O(N2).
Approach 2 – Using Pointers
A better approach is to use two pointers to represent the left and right bars of the container. Let’s call the two pointers left and right.
The approach is as follows (we’ll use the list [2, 1, 10, 2, 5, 4, 8, 3, 7] to demonstrate).
Step 1
Start with the greatest possible base for the rectangle. In other words, let left point to the first bar and right to the last bar.
Given that the base of the rectangle is now the greatest, the only way to increase the area of the rectangle is to try to increase its height. We doing that by shifting either the left or right pointer inwards.
Step 2
To shift the pointers, we need to first determine which pointer to shift. To do that, we check the height of the two bars.
Given that the container can only contain water up to the height of the shorter bar (any water above that height will spill out), changing the height of longer bar does not increase the height of the rectangle.
Hence, we’ll shift the pointer of the shorter bar. In the example above, we’ll shift the left pointer.
Step 3
We keep shifting the pointer of the shorter bar until we get an increase in height. That happens at the third bar in the example above.
Step 4
Once we get an increase in height, we calculate the area formed by this new bar and compare it with the current area. If the new area is greater, we update the result.
Step 5
We repeat steps 2 to 4 and keep shifting the left (or right) pointer to try to get a greater area.
Step 6
We keep doing that until the left pointer is no longer smaller than the right pointer.
When that happens, we return the result of the greatest area found.
Graphical Illustration
Here’s a graphical illustration of how the approach works for our example:
Suggested Solution
Here’s the suggested solution for the Container with Most Water problem in Python:
def maxArea(height):
left = 0
right = len(height) - 1
result = 0
currentHeight = 0
while left < right:
currentHeight = min(height[left], height[right])
result = max(result, (right - left)*currentHeight)
if height[left] < height[right]:
left += 1
while height[left] < currentHeight:
left += 1
else:
right -= 1
while height[right] < currentHeight:
right -= 1
return result
Here, we first define a function called maxArea() that has one parameter – height.
Next, we declare and initialise two variables – left and right.
left points to the left edge of the container while right points to the right. We initialize left to 0 (i.e. it points to the first bar) and right to len(height) - 1 (i.e. it points to the last bar). This gives the container the greatest possible base.
We also declare two variables called result and currentHeight and initialize them to zero.
Shifting the Pointers
Now, we are ready to shift our left and right pointers.
We do this using the while loop from lines 7 to 19. Inside the loop, we first determine the shorter of the left and right bars and assign its height to currentHeight (on line 9).
Next, we calculate the area of the current rectangle by multiplying currentHeight with the base of the rectangle. We assign the maximum value between the current value of result and newly calculated area to result.
Next, we check if the left bar is shorter than the right bar (on line 12). If it is, the if block on lines 13 to 15 is executed and we increment the value of left by 1. We keep incrementing left by 1 until we get a height that is greater than the current height. This is shown as step 3 in the infographics above.
On the other hand, if the left bar is not shorter than the right bar, the else block on lines 17 to 19 is executed. We keep decrementing the value of right by 1 until we get a height that is greater than the current height. This is shown as step 5 in the infographics above.
Each time we finish updating the value of left (or right), we return to the top of the while loop and check if left is smaller than right (on line 7).
If it is, we execute the while loop again.
We keep executing the while loop until left is no longer smaller than right.
When that happens, result stores the value of the greatest area and we return its value on line 21.
An Example
Let’s look at an example of how this code works.
We’ll use the list [2, 1, 10, 2, 5, 4, 8, 3, 7] to illustrate.
The first time the while loop runs,
left = 0 right = 8 currentHeight = min(height[0], height[8]) = min(2, 7) = 2 result = max(result, (right - left)*currentHeight) = max(0, (8 - 0) * 2) = max(0, 16) = 16
The value of result is updated to 16.
After updating the value of result, we check if height[left] is smaller than height[right] (on line 12).
As it is, the if block from lines 13 to 15 is executed and left is updated to 2 (which is the index of the 3rd bar)
After updating the value of left, we return to line 7 to test if left is smaller than right. As it is, we execute the while loop again.
The second time the while loop runs,
left = 2 right = 8 currentHeight = min(height[2], height[8]) = min(10, 7) = 7 result = max(16, (8-2)*7) = max(16, 42) = 42
The value of result is updated to 42.
After updating the value of result, we execute the else block (as height[left] is not smaller than height[right]) on lines 17 to 19 to update the value of right to 6.
Since left is smaller than right, we execute the while loop again.
The third time the while loop runs,
left = 2 right = 6 currentHeight = min(height[2], height[6]) = min(10, 8) = 8 result = max(42, (6-2)*8) = max(42, 32) = 42
The value of result is NOT updated as 32 is smaller than 42.
We keep updating the values of left (or right) until left is no longer smaller than right.
When that happens, we exit the while loop and return the value of result.
In our example, we return the value 42.
With that, the function is complete.