Two Pointers
Container With Most Water
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given an array heights where each element represents the height of a vertical line, pick two lines to form a container. Return the maximum area (amount of water) the container can hold.
What is area? Width × height, where width is the distance between walls, and height is the shorter wall (water overflows at the shorter wall).
Example 1:
heights = [3, 4, 1, 2, 2, 4, 1, 3, 2]
Output:
21 # walls at indices 0 and 7 (both height 3): width=7, height=3, area=21
Example 2:
heights = [1, 2, 1]
Output:
2 # walls at indices 0 and 2: width=2, height=min(1,1)=1, area=2
Understanding the Problem
Picture vertical lines on a graph—each line's height comes from the array. You pick any two lines to act as the walls of a container (like a fish tank). The "area" is simply how much water this container can hold.
What is area? Just width × height:
- Width: How far apart the two walls are (right_index - left_index)
- Height: The shorter wall's height (min(heights[left], heights[right]))
Why the shorter wall? Imagine filling the container with water—it would overflow at the level of the shorter wall. If one wall is height 10 and the other is height 3, water only fills up to height 3 before spilling over.
Area formula: width × min(left_height, right_height)
Why Does Two-Pointer Work Here?
Two-pointers are generally perceived to work on sorted arrays and that's a common pattern, but not a strict rule. Two-pointer works whenever we can eliminate possibilities by moving pointers intelligently.
In this problem, the array isn't sorted—but we don't need it to be. We start with the widest possible container (pointers at both ends) and can eliminate suboptimal containers based on a simple observation: moving the taller wall inward can never help us because:
- The width decreases
- The height is still limited by the shorter wall
So we always move the pointer pointing to the shorter wall, hoping to find a taller one.
Solution
Visualization
Try these examples:
def max_area(heights):left, right = 0, len(heights) - 1current_max = 0while left < right:width = right - leftheight = min(heights[left], heights[right])current_area = width * heightcurrent_max = max(current_max, current_area)if heights[left] < heights[right]:left += 1else:right -= 1return current_max
container with most water
0 / 26
Explanation
We can solve this in linear time because we systematically eliminate containers that can't possibly be better. Starting with pointers at opposite ends, the current container (outlined in blue) can hold 16 units of water.
The calculation: width is 8 - 0 = 8, height is min(3, 2) = 2 (limited by the shorter wall on the right), so area is 8 × 2 = 16.
But, which pointer should we move?
The right wall (height 2) is shorter than the left wall (height 3). If we move the left pointer inward, we'd get a narrower container but the height would still be capped at 2 (by the right wall). That can only make things worse or equal—never better.
So we should move the shorter wall's pointer (right), hoping to find a taller wall that could increase our area.
What if both walls are the same height? Then it doesn't matter which one you move — both are equally "the shorter wall." Neither side can produce a better container with the other wall held fixed, because the width would shrink while the height stays the same (or drops). So moving either pointer is safe. In our code, the else branch handles this by moving the right pointer, but moving the left would work just as well.
Let's verify this intuition. Here are all containers ending at the right pointer (current container = 16):
And the areas of all other containers starting at the left pointer:
Notice that every container ending at the right pointer (with smaller width) holds ≤16 units of water. This confirms our intuition: keeping the shorter wall and narrowing the container can't help. So we move the right pointer inward, eliminating all these suboptimal containers in one step.
This gives us a new container with a area of 21, which becomes the new maximum.
Complexity
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) where n is the length of the input array. The two pointers start at opposite ends and only ever move toward each other, so each element is visited at most once before they meet. We do constant work at every step, which gives us a single linear pass.
Space Complexity: O(1) we only track the two pointers and a running maximum. No matter how large the input gets, the extra memory we use stays fixed.
Mark as read
Your account is free and you can post anonymously if you choose.