Search
⌘K
Get Premium
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
Python
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.
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.
Mark as read
Your account is free and you can post anonymously if you choose.