Container With Most Water

Medium Problem 20 of 151 Java and Python

Problem

You are given an array height of n vertical lines; line i stands at position i with height height[i].

Choose two lines that, together with the x-axis, form a container holding the most water. Return that maximum amount. The container cannot be tilted.

Example 1

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Why: Lines at positions 1 (height 8) and 8 (height 7): width 7 × height 7 = 49.

Example 2

Input: height = [1, 1]
Output: 1

Constraints

2 ≤ n ≤ 10⁵
0 ≤ height[i] ≤ 10⁴

Explanation

Water held = width × the shorter line. Start with the widest container, using both ends.

To have any chance of more water you must narrow the width, so you need a taller short side. Moving the taller line inwards can never help: the short line still limits the height. So always move the shorter one.

Approach 1 · Naive

Every pair of lines

Time O(n²)
Space O(1)

Compute the water for every pair (i, j) and keep the maximum.

For every i < j, area = (j - i) × min(height[i], height[j]).
Track the largest area.

Java

class Solution {
    public int maxArea(int[] height) {
        int best = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                best = Math.max(best, (j - i) * Math.min(height[i], height[j]));
            }
        }
        return best;
    }
}

Python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        best = 0
        for i in range(len(height)):
            for j in range(i + 1, len(height)):
                best = max(best, (j - i) * min(height[i], height[j]))
        return best

Approach 2 · Optimal

Two pointers, move the shorter line

Time O(n)
Space O(1)

Start at both ends. Record the area, then move whichever pointer has the shorter line.

Set left = 0, right = n - 1.
Update the best with (right - left) × min(height[left], height[right]).
If height[left] < height[right], move left right; otherwise move right left.

Java

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int best = 0;
        while (left < right) {
            int area = (right - left) * Math.min(height[left], height[right]);
            best = Math.max(best, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }
}

Python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        best = 0
        while left < right:
            best = max(best, (right - left) * min(height[left], height[right]))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return best

Complexity compared

Approach	Time	Space
Naive Every pair of lines	O(n²)	O(1)
Optimal Two pointers, move the shorter line	O(n)	O(1)

Key takeaways

Be ready to explain why moving the shorter line is safe: every container it could form with the taller line is no better than the current one.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem