Container With Most Water

Problem Statement

You are given an integer array height of length n. Picture n vertical lines on the x-axis: line i stands at position i and is height[i] units tall. Choose two of the lines; together with the x-axis they form an open container. The water it holds has width equal to the distance between the two lines and depth equal to the shorter of the two lines.

Return the largest amount of water any pair of lines can hold. The container cannot be tilted, and lines between the chosen pair do not get in the way.

Examples

Example 1:

Input: height = [2,7,3,6,4,8,1]
Output: 28
Explanation: Lines at index 1 (height 7) and index 5 (height 8) are 4 apart.
The water depth is min(7, 8) = 7, so the area is 4 * 7 = 28.

Example 2:

Input: height = [5,5]
Output: 5
Explanation: The only pair is 1 apart with depth 5.

Example 3:

Input: height = [3,0,0,0,3]
Output: 12
Explanation: The two outer lines are 4 apart and both are 3 tall: 4 * 3 = 12.

Constraints

• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

Approach 1: Brute Force (Every Pair)

Algorithm

Try every pair of lines and compute the water each pair holds.

1. Set best = 0.
2. For every i and every j > i, compute (j - i) * min(height[i], height[j]).
3. Keep the largest value and return it.

This is correct but checks about n²/2 pairs, which is too slow for n = 10^5.

Implementation

Python:

from typing import List


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

Java:

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

Go:

func maxArea(height []int) int {
    best := 0
    n := len(height)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            area := (j - i) * min(height[i], height[j])
            best = max(best, area)
        }
    }
    return best
}

JavaScript:

function maxArea(height) {
    let best = 0;
    const n = height.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const area = (j - i) * Math.min(height[i], height[j]);
            best = Math.max(best, area);
        }
    }
    return best;
}

C#:

using System;

public class Solution {
    public int MaxArea(int[] height) {
        int best = 0;
        int n = height.Length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int area = (j - i) * Math.Min(height[i], height[j]);
                best = Math.Max(best, area);
            }
        }
        return best;
    }
}

C++:

#include <algorithm>
#include <vector>
using namespace std;

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

Complexity Analysis

• Time: O(n²): every pair of lines is examined once.
• Space: O(1).

Approach 2: Two Pointers (Optimal)

Algorithm

Start with the widest container: left = 0 and right = n - 1. Its area is limited by the shorter of the two lines.

Now consider the shorter line, say height[left] <= height[right]. Every other container that uses left with some line between the pointers is narrower, and its depth can never exceed height[left]. So none of those containers can beat the one we just measured. Line left has nothing more to offer, and we can discard it by moving left one step right. The same argument applies to right when it is the shorter one. Each step throws away exactly one line, so after n - 1 steps every line has been considered against its best partner.

1. Set left = 0, right = n - 1, best = 0.
2. While left < right:
   • Compute area = (right - left) * min(height[left], height[right]) and update best.
   • If height[left] < height[right], move left right; otherwise move right left.
3. Return best.

When the two heights are equal, moving either pointer is safe: any container keeping one of them is narrower and no deeper than the current one.

The largest possible area is (10^5 - 1) * 10^4, just under 10^9, so a 32-bit integer is enough.

Implementation

Python:

from typing import List


class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        best = 0
        while left < right:
            # Depth is limited by the shorter line
            area = (right - left) * min(height[left], height[right])
            best = max(best, area)
            # The shorter line can't do better with any narrower partner
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return best

Java:

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int best = 0;
        while (left < right) {
            // Depth is limited by the shorter line
            int area = (right - left) * Math.min(height[left], height[right]);
            best = Math.max(best, area);
            // The shorter line can't do better with any narrower partner
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }
}

Go:

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    best := 0
    for left < right {
        // Depth is limited by the shorter line
        area := (right - left) * min(height[left], height[right])
        best = max(best, area)
        // The shorter line can't do better with any narrower partner
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return best
}

JavaScript:

function maxArea(height) {
    let left = 0, right = height.length - 1;
    let best = 0;
    while (left < right) {
        // Depth is limited by the shorter line
        const area = (right - left) * Math.min(height[left], height[right]);
        best = Math.max(best, area);
        // The shorter line can't do better with any narrower partner
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return best;
}

C#:

using System;

public class Solution {
    public int MaxArea(int[] height) {
        int left = 0, right = height.Length - 1;
        int best = 0;
        while (left < right) {
            // Depth is limited by the shorter line
            int area = (right - left) * Math.Min(height[left], height[right]);
            best = Math.Max(best, area);
            // The shorter line can't do better with any narrower partner
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }
}

C++:

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = (int)height.size() - 1;
        int best = 0;
        while (left < right) {
            // Depth is limited by the shorter line
            int area = (right - left) * min(height[left], height[right]);
            best = max(best, area);
            // The shorter line can't do better with any narrower partner
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }
};

Complexity Analysis

• Time: O(n): each iteration moves one pointer inward, so the loop runs exactly n - 1 times.
• Space: O(1).

Key Insights

1. Area = width x shorter line. The taller line never limits the water, so only the shorter line matters for the current pair.
2. Discard the shorter line. Any narrower container that keeps the shorter line is capped at the same depth with less width, so it can never win. That one observation turns O(n²) into O(n).
3. Width only shrinks. Moving inward always loses width, so the only hope for a bigger area is a taller limiting line, which you can only find by moving the shorter pointer.
4. Not the same as Trapping Rain Water. Here only two lines matter and the lines in between are ignored; in Trapping Rain Water every bar holds water above it.

Edge Cases

1. Two lines: [5,5] returns 5; [0,9] returns 0.
2. All zeros: [0,0,0] returns 0.
3. Strictly increasing heights: [1,2,3,4,5] returns 6 (index 1 and index 4: width 3, depth 2, or index 2 and index 4: width 2, depth 3).
4. Tall lines at both ends: [3,0,0,0,3] returns 12; the pointers find it on the first step.
5. Largest input: 10^5 lines all 10^4 tall gives 99999 * 10000 = 999990000, which still fits in a signed 32-bit integer.

Common Mistakes

1. Moving the taller pointer. That can skip the optimal pair; always move the shorter one.
2. Using max instead of min for depth. Water spills over the shorter line.
3. Forgetting the width. The width is right - left, not right - left + 1; adjacent lines are 1 apart.
4. Confusing it with Trapping Rain Water and summing water over every bar.
5. Assuming overflow is impossible without checking. It is safe here (under 10^9), but say so; with larger limits you would need 64-bit area values.

Interview Tips

1. Give the O(n²) idea in one line, then ask “can we avoid checking every pair?” and introduce the two pointers.
2. Prove the greedy step. The interviewer will almost always ask why moving the shorter line is safe. Have the “narrower and no deeper” argument ready.
3. Trace a short example like [2,7,3,6,4,8,1] to show the pointers converging and best updating.
4. Mention the tie case (equal heights) and why moving either side is fine.

Follow-up Questions

1. Trapping Rain Water (LC 42): count water above every bar instead of choosing two lines.
2. Return the indices of the best pair, not just the area: store left and right whenever best improves.
3. Skip lines that can’t help: after moving a pointer, keep moving while the new line is no taller than the one you just left. Same worst case, often faster in practice.
4. Largest Rectangle in Histogram (LC 84): a rectangle must fit under every bar in its range, which needs a monotonic stack.
5. Two-dimensional version: Trapping Rain Water II uses a min-heap over the boundary cells.

Related Problems

• Trapping Rain Water
• Three Sum
• Two Sum
• Largest Rectangle in Histogram