Problem statement

You are given an array height of length n; the i-th vertical line goes from (i, 0) to (i, height[i]). Find two lines that, with the x-axis, form a container holding the most water, and return that maximum amount.

The container may not be slanted.

Example 1

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

Example 2

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

Constraints

• 2 <= height.length <= 30
• 0 <= height[i] <= 100

Hints for Container With Most Water

1. Hint 1

   Area = min(h[l], h[r]) × (r - l).

2. Hint 2

   Moving the taller side inward can never help — always move the shorter one.

How to solve Container With Most Water

The area of a container is min(height[l], height[r]) * (r - l) — bounded by the shorter wall. Start at the widest pair and always move the shorter wall inward. Moving the taller one is provably pointless, so a single sweep finds the maximum.

Approach

1. Put l at the first line and r at the last, and track the best area seen.
2. Compute min(height[l], height[r]) * (r - l) and update the best.
3. Move whichever pointer refers to the shorter line inward.
4. Stop when the pointers meet.

Why it works

Suppose height[l] < height[r]. Any container using l with a closer right wall has width strictly less than r - l and height still capped by height[l], so its area is strictly smaller — every pair involving l other than the current one is already beaten. Discarding l therefore loses nothing, and by symmetry the same holds for r when it is shorter. Each step retires one index, so all candidates that could win are examined in linear time.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Move the shorter side. Moving the taller one can skip the optimum, since the shorter side keeps capping the height.
• The height is the min of the two walls, not the max or the sum.
• When the two walls are equal it does not matter which you move — the same argument rules out both.
• Width is the index distance r - l, not r - l + 1.

Reference solution

Python

from typing import List

def maxArea(height: List[int]) -> int:
    l, r = 0, len(height) - 1
    best = 0
    while l < r:
        best = max(best, min(height[l], height[r]) * (r - l))
        if height[l] < height[r]:
            l += 1
        else:
            r -= 1
    return best

Java

public static int maxArea(int[] height) {
    int l = 0, r = height.length - 1, best = 0;
    while (l < r) {
        int h = Math.min(height[l], height[r]);
        int area = h * (r - l);
        if (area > best) best = area;
        if (height[l] < height[r]) l++;
        else r--;
    }
    return best;
}

C++

int maxArea(vector<int>& height) {
    int l = 0, r = (int) height.size() - 1, best = 0;
    while (l < r) {
        int h = min(height[l], height[r]);
        int area = h * (r - l);
        if (area > best) best = area;
        if (height[l] < height[r]) l++;
        else r--;
    }
    return best;
}

JavaScript

var maxArea = function(height) {
    let l = 0, r = height.length - 1, best = 0;
    while (l < r) {
        best = Math.max(best, Math.min(height[l], height[r]) * (r - l));
        if (height[l] < height[r]) l++;
        else r--;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium