Container With Most Water

Q: What is the time complexity of Container With Most Water?

The two-pointer solution runs in O(n) time and O(1) extra space, since each step moves one pointer one position inward. Checking every pair takes O(n²), and sorting the lines by height takes O(n log n).

Q: 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 no taller. None of them can beat the container you measured, so the shorter line can go without losing the answer.

Q: Is Container With Most Water a greedy problem?

Yes. Each step makes a local choice that is never undone: drop the shorter line. The choice is safe because every container it rules out is no better than one already measured, which is why the problem is filed under both greedy and two pointers.

MediumTwo pointers Greedy

+10

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

maxArea(height: integer-array) → integer

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 ≤ 10⁴
0 ≤ height[i] ≤ 10⁴
The answer is at most 10⁸, 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, heights 7 and 6, stand 6 apart and hold 6 × 6 = 36. The two tallest lines, the 7s at positions 1 and 5, hold only 7 × 4 = 28.

Follow-up

Here the lines between your two are ignored. If every line were a solid bar, how much water would collect between them all? Can you compute that in O(n) too?

Solution

Checking all n²/2 pairs means 5 × 10^7 products for 10^4 lines. The water depends only on the shorter line of a pair, so once 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 into one pass from both ends.

Check every pair

Correct, but does not finish on the largest tests

Intuition

A pair i < j holds min(height[i], height[j]) × (j - i): water spills over the shorter wall, and the floor is j - i wide. Try every pair and keep the largest.

n lines give n(n-1)/2 pairs: about 5 × 10^7 for 10^4 lines, and four times as many each time n doubles.

Algorithm

Set best to 0.
For each i, and each j after it, compute min(height[i], height[j]) × (j - i).
Keep the larger of best and 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 best

Tallest lines first

Intuition

If line i is the shorter side of a container, its partner can be any line at least as tall. So the best such container pairs it with the farthest line at least as tall.

Place the lines from tallest to shortest. When line i comes up, every placed line is at least as tall, and the farthest one is the leftmost or rightmost placed index, lo or hi. So line i holds at best height[i] × max(i - lo, hi - i), and the best container is counted when its shorter line comes up. Of two equal lines, the second one placed sees the first as a partner.

In the first example the 7s at positions 1 and 5 come first and hold 28. The 6 at position 7 then sees lo = 1 and holds 36. The sort costs O(n log n) time and O(n) memory.

Algorithm

Sort the indices by height, tallest first.
Set lo and hi to the first index of that order and best to 0.
For each next index i, compute height[i] times the larger of i - lo and hi - i, and keep the best value.
Update lo and hi to include i.
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 best

Two pointers from both ends

Intuition

Start with the widest container, left = 0 and right = n-1, and say height[left] ≤ height[right]. Every other container that uses line left pairs it with a closer line, so it is narrower and no taller than height[left]. None of them beats the water you measured, so line left is finished and left moves one step right. On equal heights both lines are finished, so moving either is fine.

Each step retires one line, so the pointers meet after n-1 steps. The best pair is never skipped: when the first of its two lines is dropped, the container measured at that moment holds at least as much.

On the first example, positions 0 and 7 hold 21 and the 3 is dropped. Positions 1 and 7 hold 36 and the 6 is dropped. The rest hold 15, 28, 12, 10 and 2.

Algorithm

Set left = 0, right = n-1 and best = 0.
While left < right, compute min(height[left], height[right]) × (right - left) and keep the best value.
If height[left] < height[right], move left one step right. Otherwise move right one 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

Moving the taller line. On the first example that returns 21 instead of 36: the 6 at position 7 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.
Measuring the width as j - i + 1. Lines at positions i and j stand j - i apart, so [4, 4] holds 4, not 8.
Assuming the answer uses the tallest lines or the outer pair. In the first example the two 7s hold 28 and the outer pair 21, while the answer is 36.

Frequently asked questions3

What is the time complexity of Container With Most Water?

The two-pointer solution runs in O(n) time and O(1) extra space, since each step moves one pointer one position inward. 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 no taller. None of them can beat the container you measured, so the shorter line can go without losing the answer.

Is Container With Most Water a greedy problem?

Yes. Each step makes a local choice that is never undone: drop the shorter line. The choice is safe because every container it rules out is no better than one already measured, which is why the problem is filed under both greedy and two pointers.

def maxArea(height):
    # Write code here

Test #1

Test #2

Argument

height = [3, 7, 2, 5, 4, 7, 3, 6]

Expected Output

Container With Most Water

Function

Constraints

Examples

Hints

Solution

Check every pair

Tallest lines first

Two pointers from both ends

Pitfalls and edge cases

Frequently asked questions3

Similar problems