Container With Most Water

Problem Description

You are given an integer array height of length n. There are n vertical lines where the endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container holding the most water. Return the maximum amount of water a container can store.

You may not slant the container.

Examples

Constraints

• n == height.length
• 2 ≤ n ≤ 10⁵
• 0 ≤ height[i] ≤ 10⁴

Move the Shorter Wall, Never the Taller One

Start with the widest possible container: left at 0, right at n-1. The water held is min(height[left], height[right]) * (right - left). To find a larger container, you must either increase the height or the width. Width only decreases as you move pointers inward, so you need to increase height. Moving the shorter wall inward is the only choice that can possibly find a taller wall. Moving the taller wall inward is guaranteed to reduce width while the height is still bounded by the shorter wall, so it can only decrease the area or keep it the same.

This argument proves the greedy is correct: always move the pointer at the shorter wall.

Solution 1: Brute Force

Check every pair of lines.

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

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

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxArea(std::vector<int>& height) {
        int maxWater = 0;
        for (int i = 0; i < height.size(); i++)
            for (int j = i + 1; j < height.size(); j++)
                maxWater = std::max(maxWater, std::min(height[i], height[j]) * (j - i));
        return maxWater;
    }
};

Complexity Analysis:

• Time Complexity: O(n²). Every pair checked.
• Space Complexity: O(1). No extra data structure.

Where it breaks: at n = 10⁵, this is 5 billion iterations. TLE every time.

Solution 2: Two Pointers (Greedy)

Start from both ends and always move the pointer at the shorter wall inward.

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxWater = 0;
        while (left < right) {
            maxWater = Math.max(maxWater, Math.min(height[left], height[right]) * (right - left));
            // move the shorter wall inward; moving the taller one can only reduce area
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxWater;
    }
}

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        max_water = 0
        while left < right:
            max_water = max(max_water, min(height[left], height[right]) * (right - left))
            # move the shorter wall inward; moving the taller one can only reduce area
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_water

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxArea(std::vector<int>& height) {
        int left = 0, right = height.size() - 1, maxWater = 0;
        while (left < right) {
            maxWater = std::max(maxWater, std::min(height[left], height[right]) * (right - left));
            // move the shorter wall inward; moving the taller one can only reduce area
            if (height[left] < height[right]) left++;
            else right--;
        }
        return maxWater;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Each pointer moves at most n times total.
• Space Complexity: O(1). Two pointer variables.

Where it breaks: if both walls are equal height, you move either one (the else branch moves right). This is correct, but you might wonder if you’re missing the case where both should move. You’re not: if equal heights, moving either one can’t increase the height of the new smaller wall, so one move is sufficient.

Common Mistakes

• Computing area as height[left] * (right - left) instead of min(height[left], height[right]) * (right - left). The container height is limited by the shorter wall.
• Moving the taller wall. The intuition says “maybe there’s a taller wall further in,” but moving the shorter wall already explores that. Moving the taller wall abandons a potentially higher pairing.
• Not computing the area before moving the pointer. Compute first, then decide which pointer to advance.

Frequently Asked Questions

Why is it always correct to move the shorter wall? If height[left] < height[right], any container using left as one wall and a pointer between left and right as the other will have a smaller width and the same or smaller height (bounded by height[left]). So no better container exists using left as the left wall. It’s safe to discard left.

What if you always move both pointers inward? You’d miss some pairs. The two-pointer approach works specifically because you’re only moving one pointer at a time, making a greedy decision each step.

How do you handle ties in wall height? Move either one. Both choices are equivalent: neither wall is strictly more promising than the other.

← All Problems