Container With Most Water

Mediumtwo pointersAmazonGoogleGoldman SachsBloomberg

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

Find two lines that together with the x-axis form a container, such that the container contains the **most water**.

Return the maximum amount of water a container can store.

**Notice** that you may not slant the container.

Examples

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

Output:49

Explanation:The lines at index 1 (height 8) and index 8 (height 7) form a container with area = min(8,7) * (8-1) = 49.

Input:height = [1,1]

Output:1

Explanation:The only container is between index 0 and 1, with area = min(1,1) * 1 = 1.

Constraints

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

💡 Hints

Hint 1

Start with the widest container (left=0, right=n-1) and try to find a taller one.

Hint 2

Always move the pointer pointing to the shorter line — keeping the shorter line can never increase the area.

Algorithm Complexity

Official asymptotic Big-O runtime and auxiliary memory analysis

Linear

Algorithmic Approach

Two pointers from both ends. Calculate area at each position. Move the pointer with the shorter height — keeping the shorter line can't produce a larger area since width is already decreasing.

Time ComplexityO(n)

Why:

Two pointers start at opposite ends and move toward each other, inspecting each line at most once.

Space ComplexityO(1)

Why:

Only requires two index pointers and a scalar variable to track maximum area in O(1) memory.

Big-O Growth CurveLinear (O(N))

Execution time scales directly in proportion to the input size.

🌍 Real-World Use Cases

AmazonWarehouse space optimization

Finding the optimal placement of two dividers in a warehouse to maximize storage volume between them.

Goldman SachsTrading range analysis

Identifying the maximum potential profit window between two price points in a time series.

🔍 Dry Run

Solution⏱ O(n) | 💾 O(1)

Line2

left=0number

right=5number

maxArea=0number

Initialize left=0 (height 1), right=5 (height 7), maxArea=0