Difficulty: MediumTwo Pointers

Container With Most Water

Problem in Plain English

Given an array height where each entry marks the height of a vertical line, choose two lines that with the x-axis hold the most water and return that maximum area. A pair at distance w with shorter height h holds w * h units.

Problem Statement

You are given an integer array height of length n. The endpoints of line i are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container holding the most water, and return that maximum amount. The container may not be slanted, so a pair i < j holds min(height[i], height[j]) * (j - i) units.

Constraints

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

Examples

Example 1

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

Lines 1 (height 8) and 8 (height 7) give min(8, 7) * (8 - 1) = 49, which is larger than every other pair.

Example 2

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

The only pair holds min(1, 1) * 1 = 1.

Example 3

Input: height = [0, 2, 0]
Output: 0

Every pair includes a zero-height wall, so every container has zero area despite the tall middle line.

Example 4

Input: height = [5, 5, 5, 5]
Output: 15

All pairs have limiting height 5. The endpoints give the greatest width, 3, and area 5 * 3 = 15; moving either pointer on a tie is safe.

Intuition

A container is limited by its shorter wall, so its area is width times the smaller height. Example 1 pairs index 1, height 8, with index 8, height 7: width 7 times height 7 gives 49. Begin with the widest pair. As width shrinks, improvement requires a taller limiting wall, so discard the shorter endpoint and keep looking inward. Lines between the endpoints do not subtract from the container area.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

The answer is simply the best of all pairs, so measuring every pair and remembering the largest area is always correct. It is just too slow for the upper limits.

Step-by-Step Logic

Initialize maxArea = 0. For every left index i, examine every later right index j starting at i + 1; distinct walls require i < j.
Compute width = j - i and limitingHeight = min(height[i], height[j]). Multiply them to get the candidate area.
Update maxArea with the larger of its previous value and this candidate. In Example 1, pairs starting at index 0 eventually raise it to 8.
Continue all pairs: at i = 1 and j = 8, min(8, 7) * 7 = 49 raises the maximum. The remaining candidates cannot exceed it.
After every pair is checked, return maxArea = 49. The complete table includes all 36 pair checks.

Why It Works

Every container consists of a unique pair i < j, and the nested loops examine each such pair exactly once. The smaller endpoint height is the highest water level both walls can support, and j - i is their horizontal separation. maxArea retains the largest measured area after each check, so the final value is the maximum over all legal containers.

Dry Run

Brute Force: variable states at each step
i	j	Heights	Limiting height	Width	Area	maxArea after
0	1	1, 8	1	1	1	1
0	2	1, 6	1	2	2	2
0	3	1, 2	1	3	3	3
0	4	1, 5	1	4	4	4
0	5	1, 4	1	5	5	5
0	6	1, 8	1	6	6	6
0	7	1, 3	1	7	7	7
0	8	1, 7	1	8	8	8
1	2	8, 6	6	1	6	8
1	3	8, 2	2	2	4	8
1	4	8, 5	5	3	15	15
1	5	8, 4	4	4	16	16
1	6	8, 8	8	5	40	40
1	7	8, 3	3	6	18	40
1	8	8, 7	7	7	49	49
2	3	6, 2	2	1	2	49
2	4	6, 5	5	2	10	49
2	5	6, 4	4	3	12	49
2	6	6, 8	6	4	24	49
2	7	6, 3	3	5	15	49
2	8	6, 7	6	6	36	49
3	4	2, 5	2	1	2	49
3	5	2, 4	2	2	4	49
3	6	2, 8	2	3	6	49
3	7	2, 3	2	4	8	49
3	8	2, 7	2	5	10	49
4	5	5, 4	4	1	4	49
4	6	5, 8	5	2	10	49
4	7	5, 3	3	3	9	49
4	8	5, 7	5	4	20	49
5	6	4, 8	4	1	4	49
5	7	4, 3	3	2	6	49
5	8	4, 7	4	3	12	49
6	7	8, 3	3	1	3	49
6	8	8, 7	7	2	14	49
7	8	3, 7	3	1	3	49
done	none	none	none	none	none	return 49

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

For n lines, the loops make n(n - 1)/2 pair checks, each using constant-time arithmetic: O(n^2) time. Only loop indices, a candidate area, and the running maximum are stored, so extra space is O(1). The input is not modified. At the maximum bounds, area is at most 10000 * 99999 = 999990000, which fits Java int and is exactly representable in JavaScript. This baseline is impractical at n = 100000.

Code

Solution.java

1class Solution {2    public int maxArea(int[] height) {3        int maxArea = 0;4        for (int i = 0; i < height.length; i++) {5            for (int j = i + 1; j < height.length; j++) {6                int area = Math.min(height[i], height[j]) * (j - i);7                maxArea = Math.max(maxArea, area);8            }9        }10        return maxArea;11    }12}

Hints

Hint 1

The area of a pair is set by the shorter line, so which side limits the current container?

Hint 2

Starting from the outermost pair gives the maximum width; what must improve to beat its area?

Hint 3

Only moving the shorter line inward can raise the limiting height, so the taller side can safely stay.

Edge Cases

Exactly two lines such as [1, 1], where the single pair is the answer.
Zero-height lines like [0, 2, 0], where any pair touching a 0 holds nothing.
Equal heights such as [5, 5, 5, 5], where the outermost pair wins and either pointer may move on ties.

Common Mistakes and Interview Tips

Advancing the taller line instead of the shorter one, which shrinks the width while the limiting height cannot grow.
Measuring height with max instead of min, which credits water the shorter wall cannot hold.
Enumerating all $O(n^2)$ pairs, which is impractical at n = 10^5.
Using j - i + 1 as width counts positions rather than the distance between walls.
Confusing this problem with trapped rainwater: intermediate lines do not subtract from the chosen container area.
Interview tip: prove which entire family of pairs is discarded by moving the shorter wall; a taller wall merely being possible is not the full correctness argument.

Key Takeaway

When candidates are ordered pairs and one move provably cannot improve the answer, converging pointers from both ends checks only the survivors in linear time.