Container With Most Water

The problem

You are given an array height of n numbers. Each number is a vertical line: line i stands at position i and is height[i] tall.

Choose any two lines. Together with the floor, they form a container. Return the largest amount of water a container can hold. The container cannot be tilted, so the water stops at the shorter of the two lines.

Example 1

Input: height = [2, 5, 4, 1, 6, 3]

Output: 15

The lines of height 5 and 6 stand 3 positions apart. The water stops at the shorter one, so they hold 3 × 5 = 15.

height

Example 2

Input: height = [3, 3]

Output: 3

There is only one pair. It is 1 position wide and 3 tall.

Example 3

Input: height = [4, 0, 0, 4]

Output: 12

The two outer lines are both 4 tall and 3 positions apart, so they hold 3 × 4 = 12. The zeros in between do not block the water.

Constraints

• 2 ≤ n ≤ 100,000
• 0 ≤ height[i] ≤ 10,000

Clarifying questions

Is the array sorted?

No. And we must not sort it: sorting moves the lines and changes the distances.

Can a height be 0?

Yes. A line of height 0 holds no water. The formula already gives 0, so no special case.

Can we use the same line twice?

No. We need two different lines, so the width is always at least 1.

Do we return the lines or the amount?

Only the amount. If several pairs tie, it does not matter which one we find.

Can the answer overflow?

No. The largest answer is 10,000 × 99,999, just under 1,000,000,000. That fits in a 32-bit integer.

Spot the pattern

We pick a pair from an array, and the answer depends on both ends and the distance between them. That is the clue for two pointers: start one pointer at each end and move them toward each other. The hard part is knowing which pointer is safe to move.

Solutions

Brute forceO(n²)OptimalO(n)

Show all

This problem has two approaches. There is no useful step between them.

Brute force O(n²)

The idea

Try every pair of lines. For each pair, the water is the shorter line times the gap between them. Keep the largest. It is always correct, and it is a fine first answer. But with n lines there are about n × n / 2 pairs, which is too many when n is 100,000.

Walkthrough

height

i \ j	0	1	2	3	4	5
0		·	·	·	·	·
1			·	·	·	·
2				·	·	·
3					·	·
4						·
5

1. best = 0
2. for i in range(len(height)):
3. for j in range(i + 1, len(height)):
4. water = min(height[i], height[j]) * (j - i)
5. best = max(best, water)
6. return best

Check every pair of lines. The grid on the right will fill with one square per pair.

← BackStep →Play1 / 7

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: try every pair of lines and keep the best.
    // Always correct, but it checks about n * n / 2 pairs.
    public int maxArea(int[] height) {
        int best = 0;
        // j starts after i, so each pair is checked exactly once.
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                // Water stops at the shorter line. The width is the gap.
                int water = Math.min(height[i], height[j]) * (j - i);
                best = Math.max(best, water);
            }
        }
        return best;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The two lit lines measure one pair. They sit inside two loops, so they run again and again. Each run does the same small job: one min, one multiply and one max. That job does not grow with n, so each run counts as 1 step.

   1. best = 0
   2. for i in range(len(height)):
   3. for j in range(i + 1, len(height)):
   4. water = min(height[i], height[j]) * (j - i)
   5. best = max(best, water)
   6. return best

2. 2 Count the runs on Example 1

   Example 1 has 6 lines. The outer loop picks line i. The inner loop pairs it with every line to its right. Line 0 has 5 lines to its right, line 1 has 4, and so on down to line 4, which has 1.

   5 + 4 + 3 + 2 + 1 = 15 runs.

   line i	0	1	2	3	4	5
   pairs	5	4	3	2	1	0

   total

   5 + 4 + 3 + 2 + 1 = 15

3. 3 Write the count for any n

   With n lines, line 0 has n − 1 partners, line 1 has n − 2, and so on down to 1. That adds up to:

   (n − 1) + (n − 2) + … + 1 = n × (n − 1) / 2 = ½n² − ½n

   Check it with Example 1: 6 × 5 / 2 = 15.

4. 4 Keep only the part that grows fastest

   Big O only tells us how the work grows when n gets big. So we drop two things from ½n² − ½n:

   • Drop the −½n. Next to ½n² it soon stops mattering. At n = 100, ½n² is 5,000 and ½n is only 50.
   • Drop the ½. Halving every count does not change how fast the count grows. When n doubles, ½n² grows 4 times, just like n².

   What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code creates i, j, water and best. That is 4 variables for 6 lines or for 100,000 lines. The count does not depend on n, so the space is O(1). The input array does not count, because it was given to us.

   ijwaterbest

Optimal O(n)

The idea

Start with the widest container: the first and the last line. Every other container is narrower, so it can only win by being taller.

Now look at the shorter of the two lines. The water can never rise above it. If we keep it and move the other line inward, the container gets narrower and no taller. So the shorter line can never be part of a bigger container. We drop it and move that pointer inward. Then we measure again.

Why it never misses the answer: we only drop a line after showing that every container it could still make is no bigger than one we already measured.

Walkthrough

height

best

0

1. left, right = 0, len(height) - 1
2. best = 0
3. while left < right:
4. water = min(height[left], height[right]) * (right - left)
5. best = max(best, water)
6. if height[left] < height[right]:
7. left += 1
8. else:
9. right -= 1
10. return best

Start with the widest container: the first line and the last line.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Two pointers: start with the widest container and drop the
    // shorter line each step. Each line is dropped once, so n steps.
    public int maxArea(int[] height) {
        // The widest container. Any other one is narrower,
        // so it can only win by being taller.
        int left = 0, right = height.length - 1;
        int best = 0;
        while (left < right) {
            // Water stops at the shorter line, so it sets the height.
            int water = Math.min(height[left], height[right]) * (right - left);
            best = Math.max(best, water);
            // Drop the shorter line. Any container that still uses it
            // is narrower and no taller, so it can never beat this one.
            if (height[left] < height[right]) left++;
            else right--;
        }
        return best;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop measures one pair and moves one pointer. That is the same small job every time, so each run counts as 1 step. There is only one loop, and nothing inside it loops again.

   1. left, right = 0, len(height) - 1
   2. best = 0
   3. while left < right:
   4. water = min(height[left], height[right]) * (right - left)
   5. best = max(best, water)
   6. if height[left] < height[right]:
   7. left += 1
   8. else:
   9. right -= 1
   10. return best

2. 2 Count the runs on Example 1

   Example 1 has 6 lines. The loop runs while left < right. The gap between them starts at 5. Every run moves one pointer inward, so the gap shrinks by exactly 1. It reaches 0 after 5 runs, and the loop stops.

   5 runs.

   	run 1	run 2	run 3	run 4	run 5	stop
   left	0	1	1	2	3	4
   right	5	5	4	4	4	4
   gap	5	4	3	2	1	0

3. 3 Write the count for any n

   The gap starts at n − 1 and shrinks by 1 on every run, so the loop runs exactly:

   n − 1 times

   Check it with Example 1: 6 − 1 = 5.

4. 4 Keep only the part that grows fastest

   Drop the − 1. One run more or less does not change how the work grows. When n doubles, n − 1 about doubles too. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code creates left, right, water and best. That is 4 variables, whatever n is, so the space is O(1).

   leftrightwaterbest

Common mistake

Moving the taller line

The shorter line is what limits the water. Moving the taller one keeps that limit and makes the container narrower, so it can skip the best answer. When both lines are the same height, moving either one is safe.

Tested at the limits

2,000 random arrays of 2 to 12 heights, with many ties and zeros. The brute force and the two pointers gave the same answer every time.

Largest inputs	Result
100,000 heights (the most allowed), each up to 10,000. Two pointers.	0.01 s, and under 0.001 MB of extra memory: just the 4 variables.
2,000 heights. Brute force, about 2 million pairs.	0.2 s. At 100,000 heights it would check 5 billion pairs, which is why the two pointers matter.