Container With Most Water
You get a list height of non-negative integers. Line i is a vertical wall of height height[i] standing at position i. Any two lines form a container with the ground, and it holds as much water as the shorter line's height times the distance between the two lines. The other lines do not get in the way. Return the most water a single pair of lines can hold.
Function
- heightinteger-array
- the heights of the lines at positions 0, 1, 2 and so on
- Returnsinteger
- the most water two lines can hold
Constraints
2 ≤ height.length ≤ 1040 ≤ height[i] ≤ 104- The answer is at most 108, so it fits in a 32-bit integer.
Examples
- Input
- height = [3, 7, 2, 5, 4, 7, 3, 6]
- Output
- 36
- Explanation
- The lines at positions 1 and 7 have heights 7 and 6 and stand 6 apart, so they hold 6 × 6 = 36. The two tallest lines, the 7s at positions 1 and 5, hold only 7 × 4 = 28, and the outer pair holds 3 × 7 = 21.
- Input
- height = [4, 4]
- Output
- 4
- Explanation
- Two lines make exactly one container: height 4 and width 1, so it holds 4.
+15 hidden tests on Submit
Follow-up
Here the lines between the two you pick are ignored. If every line were a solid bar instead, how much water would collect between all of them? Can you compute that in O(n) as well?
Hints
Open them one at a time. Each one gives away a little more.
Start with the two outer lines: they make the widest container. Moving either end inward costs one unit of width. Which of the two lines could possibly make up for that?
The water is capped by the shorter line. Moving the taller line inward keeps that cap and loses width, so it can never help. Only replacing the shorter line has a chance.
Keep a pointer at each end. Measure the water between them and keep the best value, then move the pointer at the shorter line one step inward. Stop when the pointers meet.
Solution
There are about n²/2 pairs of lines, so for 10^4 lines checking them all means 5 × 10^7 products. The way out is that the water depends only on the shorter line of a pair: once you know a line is the shorter side of the widest container it can still form, no narrower container that uses it can do better. Two pointers turn that fact into one pass from both ends.
Check every pair
Correct, but does not finish on the largest tests
Intuition
Every container is a pair of positions i < j. Water rises until it spills over the shorter wall, and the floor between the walls is j - i wide, so the pair holds min(height[i], height[j]) × (j - i). Try every pair, keep the largest, and you have the answer by definition.
The catch is the number of pairs. n lines give n(n-1)/2 of them: about 5 × 10^7 for 10^4 lines, and four times as many each time the list doubles. A compiled language gets through that in a fraction of a second, but Python, Ruby or R need many seconds, and the count grows too fast for any language once n reaches 10^5.
Algorithm
- Set
bestto 0. - For each
i, and eachjafter it, computemin(height[i], height[j]) × (j - i). - Keep the larger of
bestand that value. - Return
best.
def maxArea(height):
n = len(height)
best = 0
for i in range(n):
for j in range(i + 1, n):
water = min(height[i], height[j]) * (j - i)
best = max(best, water)
return bestTallest lines first
Intuition
Look at a container from the side of its shorter line. If line i is the shorter side, the water is height[i] times the distance, and the partner can be any line at least as tall. So the best container in which i is the shorter side pairs it with the farthest line that is at least as tall.
To find those partners fast, place the lines from the tallest to the shortest. When line i comes up, every line placed before it is at least as tall, and the farthest of them is either the leftmost or the rightmost placed index. Track those two indices, lo and hi, and line i holds at best height[i] × max(i - lo, hi - i). The answer is the largest of these values, because the best container is counted when its shorter line comes up.
In the first example, the two 7s at positions 1 and 5 come first and hold 28. The 6 at position 7 comes next, with lo = 1 and hi = 5, and holds 6 × 6 = 36. No shorter line beats that. Equal heights can come in any order: whichever of two equal lines comes second sees the first one as a partner.
The sort costs O(n log n) and the sweep O(n), which is fast enough. It still needs O(n) memory for the order, and the next approach drops both the sort and the memory.
Algorithm
- Sort the indices by height, tallest first.
- Set
loandhito the first index of that order andbestto 0. - For each next index
i, computeheight[i]times the larger ofi - loandhi - i, and keep the best value. - Update
loandhito includei. - Return
best.
def maxArea(height):
# Indices from the tallest line to the shortest.
order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
lo = hi = order[0] # leftmost and rightmost index among the lines placed so far
best = 0
for i in order[1:]:
# Every placed line is at least as tall as line i, so line i is the
# shorter side, and its best partner is the placed line farthest away.
best = max(best, height[i] * max(i - lo, hi - i))
lo = min(lo, i)
hi = max(hi, i)
return bestTwo pointers from both ends
Intuition
Start with the widest container, left = 0 and right = n-1, and measure it. Now one of the two lines can go, and the choice is forced: drop the shorter one. Say height[left] ≤ height[right]. Every other container that uses line left pairs it with a line closer than right, so it is narrower, and its height is still at most height[left]. None of them beats the water you measured, so line left is finished and left moves one step right. Moving the taller line instead would keep the same cap on the height and lose width, so it can only lose. When the two heights are equal, both lines are finished, and moving either one is fine.
Each step retires one line for good, so after n-1 steps the pointers meet. The best pair is never skipped: the first time one of its two lines is dropped, the container measured at that moment holds at least as much water.
On [3, 7, 2, 5, 4, 7, 3, 6], positions 0 and 7 hold 3 × 7 = 21. The 3 is shorter, so left moves to 1. Positions 1 and 7 hold 6 × 6 = 36, and now the 6 is shorter, so right moves to 6. The containers that follow hold 15, 28, 12, 10 and 2, so the answer stays 36.
Algorithm
- Set
left = 0,right = n-1andbest = 0. - While
left < right, computemin(height[left], height[right]) × (right - left)and keep the best value. - If
height[left] < height[right], moveleftone step right. Otherwise moverightone step left. - When the pointers meet, return
best.
def maxArea(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
water = min(height[left], height[right]) * (right - left)
best = max(best, water)
# The shorter line cannot do better with any line closer in, so drop it.
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
Pitfalls and edge cases
The two-pointer loop is short, so the mistakes are in the details.
- Moving the taller line. On the first example that returns 21 instead of 36: the 6 at position 7 is the taller line of the first pair, so it leaves before it ever meets the 7 at position 1.
- Using the taller line, or the average of the two, as the height. Water spills over the shorter wall, so the height is the minimum.
- An off-by-one in the width. Lines at positions
iandjstandj - iapart, notj - i + 1, so two neighbours hold their shorter height times 1. - Assuming the answer uses the tallest line or the outer pair. In the first example the two 7s hold 28 and the outer pair 21, while the answer is 36.
- Overflow with larger limits. Here the water stays below 10^8, but with heights and lengths near 10^5 the product passes 2^31 and needs a 64-bit integer.
Frequently asked questions4
What is the time complexity of Container With Most Water?
The two-pointer solution runs in O(n) time and O(1) extra space. Each step moves one pointer one position inward, so there are at most n-1 steps. Checking every pair takes O(n²), and sorting the lines by height takes O(n log n).
Why move the pointer at the shorter line?
The water is capped by the shorter line. Any other container that keeps that line has a partner closer in, so it is narrower and still no taller than the shorter line. None of them can beat the container you have measured, so the shorter line can be dropped without losing the answer.
Is Container With Most Water a greedy problem?
Yes. Each step makes a local choice that is never undone, dropping the shorter line. The choice is safe because every container the step rules out is no better than one already measured. That is why the problem is filed under both greedy and two pointers.
How is Container With Most Water different from Trapping Rain Water?
Here only the two chosen lines matter and the lines between them are ignored, so the answer is a single rectangle. In Trapping Rain Water every bar is solid, and water collects above each bar up to the lower of the tallest bars on its two sides, so the answer is a sum over all positions. Both have O(n) two-pointer solutions, but the pointer rules and what you add up differ.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def maxArea(height):
# Write code hereCase 1
Case 2
Input
height = [3, 7, 2, 5, 4, 7, 3, 6]
Expected
36