Container With Most Water (LeetCode
Learn how to solve Container With Most Water using brute force and the optimal two-pointer approach. Includes intuition, dry runs, Java code, correctness proof, complexity analysis, edge cases, interview tips, and production applications.
Introduction
Container With Most Water (LeetCode #11) is one of the most important problems for learning the Two Pointer pattern.
It is frequently asked at companies like:
- Amazon
- Microsoft
- Meta
- Apple
- Netflix
- Uber
- Goldman Sachs
Interviewers use this problem to evaluate whether a candidate can:
- Recognize the greedy insight behind pointer movement
- Optimize from O(n²) to O(n)
- Explain why skipping pairs is safe
- Write clean, production-quality Java code
The key insight is:
The area is always limited by the shorter line. Moving the shorter pointer is the only move that could possibly increase the area.
If the left line is shorter:
Move left pointer right
If the right line is shorter:
Move right pointer left
This reduces the solution from quadratic time to linear time.
Problem Statement
Given an integer array height of length n, where each element represents the height of a vertical line drawn at position i, find two lines that together with the x-axis form a container that holds the most water.
Return the maximum amount of water a container can store.
You may not slant the container.
Formula
The water stored between two lines at index left and right is:
area = min(height[left], height[right]) × (right - left)
Example 1
Input
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output
49
Explanation:
Lines at index 1 and 8
height[1] = 8
height[8] = 7
Width = 8 - 1 = 7
Area = min(8, 7) × 7 = 7 × 7 = 49
Example 2
Input
height = [1, 1]
Output
1
Explanation:
Only one pair possible.
Area = min(1, 1) × (1 - 0) = 1
Example 3
Input
height = [4, 3, 2, 1, 4]
Output
16
Explanation:
Lines at index 0 and 4
height[0] = 4
height[4] = 4
Width = 4 - 0 = 4
Area = min(4, 4) × 4 = 16
Important Problem Guarantees
The LeetCode problem guarantees:
n >= 20 <= height[i] <= 10^4- The array is not sorted.
- No slanting allowed — only vertical lines.
These constraints confirm that the brute force will time out and that Two Pointer is the expected approach.
What Is the Two Pointer Technique?
The Two Pointer technique maintains two indexes and moves them inward based on which pointer limits the area.
Left Pointer → Starts at the beginning
Right Pointer → Starts at the end
Visual:
L R
↓ ↓
1 8 6 2 5 4 8 3 7
At every step:
area = min(height[left], height[right]) × (right - left)
Then:
Update maxArea
height[left] < height[right] → Move left right
height[left] > height[right] → Move right left
height[left] == height[right] → Move either (both are limiting)
Why Does Moving the Shorter Line Work?
Suppose the left line is shorter:
height[left] < height[right]
The current area is:
height[left] × (right - left)
If we move the right pointer left instead:
Width decreases
The height is still capped by height[left] (which hasn't changed)
Area can only decrease or stay the same
Therefore, moving the shorter line inward is the only direction that could produce a larger area.
Approach 1 — Brute Force
Core Idea
Check every possible pair of lines.
For each pair (i, j) where i < j:
area = min(height[i], height[j]) × (j - i)
Track the maximum area seen.
Java Code — Brute Force
public class ContainerBruteForce {
public int maxArea(int[] height) {
int maxArea = 0;
for (int left = 0;
left < height.length - 1;
left++) {
for (int right = left + 1;
right < height.length;
right++) {
int area =
Math.min(
height[left],
height[right])
* (right - left);
maxArea = Math.max(
maxArea,
area);
}
}
return maxArea;
}
}
Brute Force Complexity
| Complexity | Value |
|---|---|
| Time | O(n²) |
| Space | O(1) |
The solution uses constant memory but evaluates too many unnecessary pairs.
Why Brute Force Is Inefficient
For an array of length n, the number of possible pairs is:
n × (n - 1) / 2
For:
n = 100,000
this is approximately:
5 billion pairs
At LeetCode constraints (n up to 100,000), brute force exceeds the time limit.
Approach 2 — Optimal Two Pointer Solution
Core Idea
Initialize pointers at both ends:
int left = 0;
int right = height.length - 1;
At every step:
area = min(height[left], height[right]) × (right - left)
Update maxArea.
Then:
- Move the pointer pointing to the shorter line inward.
- If both lines are equal height, move either — both are limiting.
Repeat until the pointers meet.
Algorithm
graph TD
left_0["left = 0"] --> right_n_1["right = n - 1"]
right_n_1["right = n - 1"] --> maxArea_0["maxArea = 0"]
maxArea_0["maxArea = 0"] --> Loop_while_left_right["Loop while left right:"]
Loop_while_left_right["Loop while left right:"] --> area_min_height_left_height_["area = min(height(left), height(right)) × (right - left)"]
area_min_height_left_height_["area = min(height(left), height(right)) × (right - left)"] --> maxArea_max_maxArea_area["maxArea = max(maxArea, area)"]
maxArea_max_maxArea_area["maxArea = max(maxArea, area)"] --> height_left_height_right["height(left) = height(right)"]
height_left_height_right["height(left) = height(right)"] --> Return_maxArea["Return maxArea"]
Java Code — Optimal Solution
public class ContainerWithMostWater {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
int area =
Math.min(
height[left],
height[right])
* (right - left);
maxArea = Math.max(
maxArea,
area);
if (height[left]
<= height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
LeetCode-Style Implementation
public class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
maxArea = Math.max(
maxArea,
Math.min(
height[left],
height[right])
* (right - left));
if (height[left]
< height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
Two Pointer Flow
graph TD
Initialize_Left_and_Right["Initialize Left and Right"] --> Calculate_Area["Calculate Area"]
Calculate_Area["Calculate Area"] --> Update_maxArea["Update maxArea"]
Update_maxArea["Update maxArea"] --> Left_Line_Shorter["Left Line Shorter?"]
Left_Line_Shorter["Left Line Shorter?"] --> Repeat_Until_Left_Meets_Righ["Repeat Until Left Meets Right"]
Repeat_Until_Left_Meets_Righ["Repeat Until Left Meets Right"] --> Return_maxArea["Return maxArea"]
Detailed Dry Run
Input:
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Initial state:
left = 0
right = 8
Iteration 1
height[left] = 1
height[right] = 7
Area = min(1, 7) × (8 - 0) = 1 × 8 = 8
maxArea = 8
height[left] < height[right] → left++
Iteration 2
left = 1
right = 8
height[left] = 8
height[right] = 7
Area = min(8, 7) × (8 - 1) = 7 × 7 = 49
maxArea = 49
height[left] > height[right] → right--
Iteration 3
left = 1
right = 7
height[left] = 8
height[right] = 3
Area = min(8, 3) × (7 - 1) = 3 × 6 = 18
maxArea = 49 (unchanged)
height[left] > height[right] → right--
Iteration 4
left = 1
right = 6
height[left] = 8
height[right] = 8
Area = min(8, 8) × (6 - 1) = 8 × 5 = 40
maxArea = 49 (unchanged)
height[left] == height[right] → left++ (or right--)
Iteration 5
left = 2
right = 6
height[left] = 6
height[right] = 8
Area = min(6, 8) × (6 - 2) = 6 × 4 = 24
maxArea = 49 (unchanged)
height[left] < height[right] → left++
Pointers continue converging until left >= right.
Final answer:
49
Dry Run Table
| Step | left | right | height[L] | height[R] | Area | maxArea | Move |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 8 | 1 | 7 | 8 | 8 | L++ |
| 2 | 1 | 8 | 8 | 7 | 49 | 49 | R-- |
| 3 | 1 | 7 | 8 | 3 | 18 | 49 | R-- |
| 4 | 1 | 6 | 8 | 8 | 40 | 49 | L++ |
| 5 | 2 | 6 | 6 | 8 | 24 | 49 | L++ |
| 6 | 3 | 6 | 2 | 8 | 12 | 49 | L++ |
| 7 | 4 | 6 | 5 | 8 | 10 | 49 | L++ |
| 8 | 5 | 6 | 4 | 8 | 4 | 49 | L++ |
left = 6 = right → loop ends.
Visual Pointer Movement
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
index = 0 1 2 3 4 5 6 7 8
Step 1: L R area = 8
Step 2: L R area = 49 ← max
Step 3: L R area = 18
Step 4: L R area = 40
Step 5: L R area = 24
Step 6: L R area = 12
...
Why Moving the Shorter Pointer Is Correct
Suppose:
height[left] < height[right]
The current area is limited by height[left].
If we move the right pointer instead:
Right decreases width by 1
Height is still capped at height[left]
New area ≤ current area
Therefore, moving the right pointer cannot improve the result.
The only pointer that can possibly find a better area is the left pointer.
Why Moving the Taller Pointer Cannot Help
If height[left] >= height[right]:
Moving left right would:
Decrease width
The height is still capped by the shorter right line
Area can only decrease
Therefore, moving the right pointer is the correct choice.
Correctness Proof
Every pair (i, j) where i < j is either:
- Evaluated directly, or
- Proven to be worse than an already-evaluated pair and safely skipped.
Case 1 — Left Is the Shorter Line
When height[left] < height[right]:
All pairs (left, k) where k < right
have smaller width AND the same or smaller height (capped by height[left]).
They are all dominated by the current pair.
Moving left++ safely skips all these dominated pairs.
Case 2 — Right Is the Shorter Line
When height[left] >= height[right]:
All pairs (k, right) where k > left
have smaller width AND the same or smaller height (capped by height[right]).
They are all dominated by the current pair.
Moving right-- safely skips all these dominated pairs.
Case 3 — Equal Heights
Both lines are limiting. Either pointer can be moved. Both choices are safe because pairs skipped on either side are dominated by the current configuration.
Loop Invariant
At every iteration:
The optimal pair is always within [left, right]
When pointers meet:
All pairs have been considered or safely discarded.
The maximum area found is the global maximum.
Complexity Analysis
| Complexity | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
Each pointer moves at most n - 1 times.
Total moves:
≤ 2(n - 1) moves → O(n)
Why the Complexity Is Not O(n²)
Although there are n × (n - 1) / 2 possible pairs, the Two Pointer approach never revisits a pair.
At each step, at least one pointer moves.
The total number of steps is bounded by:
right - left ≤ n - 1
This guarantees linear time.
Why Use left < right?
The condition left < right ensures:
- The container has at least two distinct lines.
- We never compute an area with a single line.
- We never use the same index as both walls.
When left == right, no valid container can be formed.
Production-Ready Implementation
import java.util.Objects;
public class ContainerWithMostWater {
/**
* Returns the maximum water that can be contained
* between any two vertical lines in the given height array.
*
* @param height non-null array of non-negative integers,
* length >= 2
* @return maximum water volume
* @throws IllegalArgumentException if height is null or has fewer than 2 elements
*/
public int maxArea(int[] height) {
Objects.requireNonNull(height,
"height array must not be null");
if (height.length < 2) {
throw new IllegalArgumentException(
"height array must contain at least two elements");
}
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
int h = Math.min(
height[left],
height[right]);
int w = right - left;
int area = h * w;
if (area > maxArea) {
maxArea = area;
}
if (height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
Edge Cases
Minimum Array Length
Input
height = [1, 1]
Output
1
Only one pair exists.
Monotonically Increasing
Input
height = [1, 2, 3, 4, 5]
The right pointer moves left repeatedly.
The maximum area is found early.
Output
6
Explanation:
min(2, 5) × (4 - 1) = 2 × 3 = 6
min(1, 5) × (4 - 0) = 1 × 4 = 4
Actually max area:
min(2, 4) × (3 - 1) = 2 × 2 = 4
min(1, 5) × 4 = 4
min(2, 5) × 3 = 6 ← max
Monotonically Decreasing
Input
height = [5, 4, 3, 2, 1]
The left pointer moves right repeatedly.
Output
6
Explanation:
min(5, 4) × (1 - 0) = 4
min(5, 3) × (2 - 0) = 6 ← max
All Equal Heights
Input
height = [3, 3, 3, 3]
Output
9
Explanation:
Lines at index 0 and 3
min(3, 3) × 3 = 9
Single Tall Line
Input
height = [1, 1000, 1]
Output
2
Explanation:
min(1, 1) × 2 = 2
The tall middle line cannot be used as both walls.
Zeros in Array
Input
height = [0, 2, 0]
Output
0
Any pair involving a zero line holds no water.
Common Interview Mistakes
Mistake 1 — Moving the Taller Pointer
❌ Moving the pointer at the taller line
This cannot improve the area. The taller pointer is not the bottleneck. Moving the shorter pointer is the only useful action.
Mistake 2 — Moving Both Pointers
❌ left++ and right-- at every step
When heights are equal, moving only one pointer is sufficient. Moving both simultaneously skips valid pairs.
Mistake 3 — Using Area Without min
❌ area = height[left] × (right - left)
Water is limited by the shorter line. The correct formula uses min.
Mistake 4 — Using left <= right
❌ while (left <= right)
When left == right, both pointers point to the same line. No container can be formed. Use left < right.
Mistake 5 — Integer Overflow
For very large inputs:
height[i] = 10,000
n = 100,000
area = 10,000 × 100,000 = 10^9
This fits within int range (~2.1 × 10^9), but be prepared to discuss it.
For general problems where dimensions can be larger, use long:
long area = (long) h * w;
Mistake 6 — Claiming O(n log n)
❌ "The two pointers together traverse n log n elements"
Both pointers start n - 1 apart and converge. Total moves are at most n - 1. The complexity is O(n).
Mistake 7 — Not Explaining the Greedy Insight
Stating the algorithm without explaining why moving the shorter pointer is safe is a common interview mistake.
Always explain:
Moving the taller pointer cannot increase the area
because the area is already limited by the shorter line.
Mistake 8 — Brute Force After Mentioning Optimization
After saying "I'll use Two Pointer", accidentally writing a nested loop loses credibility.
Follow-Up 1 — What Is the Maximum Possible Area?
Given constraints height[i] ≤ 10^4 and n ≤ 10^5:
Max area = 10,000 × 100,000 = 10^9
This fits in a Java int. For safety, always discuss the overflow possibility.
Follow-Up 2 — Return the Indexes of the Best Pair
Track the pair that produced the maximum area.
public int[] maxAreaIndexes(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
int bestLeft = 0;
int bestRight = height.length - 1;
while (left < right) {
int area =
Math.min(height[left], height[right])
* (right - left);
if (area > maxArea) {
maxArea = area;
bestLeft = left;
bestRight = right;
}
if (height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return new int[]{bestLeft, bestRight};
}
Follow-Up 3 — What If the Array Has All Zeros?
height = [0, 0, 0, 0]
Every area computation yields 0.
The Two Pointer solution still works correctly — it returns 0.
No special case is needed because min(0, 0) × width = 0 for any width.
Follow-Up 4 — Can This Be Solved with a Stack?
A monotonic stack approach can be used, but it does not improve complexity.
Time → O(n)
Space → O(n)
The Two Pointer approach is preferred because it uses O(1) space.
Follow-Up 5 — What If Lines Can Be Slanted?
The problem explicitly disallows slanting.
If slanting were allowed, the problem would become a geometry problem requiring different techniques (e.g., computing the intersection of lines and integrating the area).
For the interview, confirm: no slanting.
Follow-Up 6 — Handling a Very Large Input File
If the array is too large to fit in memory:
Stream two chunks from each end
Maintain running max in O(1) space per step
Use disk-based two-pointer merge
This extends naturally from the in-memory algorithm.
Production Applications
The container area maximization pattern applies to real engineering systems.
Examples include:
- Cloud resource allocation: maximizing throughput between two bandwidth-limited nodes
- Load balancing: finding the two servers that together can handle the largest traffic volume
- Network capacity planning: identifying bottleneck links between endpoints
- Storage bin packing: finding the two bin sizes that maximize combined capacity
- Financial modelling: identifying two time points that maximize total return window
- Signal processing: finding the two sampling points that capture the widest signal envelope
Real-World Example — Network Bandwidth Allocation
Two data centres have bandwidth limits per link.
Find the pair of links that maximizes the total data that can flow between them.
public int maxThroughput(int[] bandwidth) {
int left = 0;
int right = bandwidth.length - 1;
int max = 0;
while (left < right) {
int throughput =
Math.min(bandwidth[left], bandwidth[right])
* (right - left);
max = Math.max(max, throughput);
if (bandwidth[left] <= bandwidth[right]) {
left++;
} else {
right--;
}
}
return max;
}
The formula and logic are identical to Container With Most Water.
Senior-Level Discussion — Why Is This Greedy Safe?
At every step, the greedy rule is:
Move the pointer at the shorter line.
This is safe because:
- The area is always bounded by the shorter line.
- Moving the taller pointer decreases width with no gain in height.
- The only hope of finding a larger area is to replace the shorter line with a taller one.
- Moving inward guarantees all pairs involving the current shorter line at a smaller width have smaller or equal area — they are dominated.
This greedy elimination is provably exhaustive — no valid pair is ever missed.
Senior-Level Discussion — Is This Dynamic Programming?
No.
This is a greedy algorithm.
At each step, a locally optimal pointer move is made.
There is no overlapping subproblem structure.
The decision at each step does not depend on decisions from previous steps — it depends only on the current heights.
Senior-Level Discussion — Why Not Binary Search?
Binary search requires a monotone condition.
The area function is not monotone across all pointer positions.
Moving left right can both increase and decrease area, depending on the heights.
Therefore, binary search cannot be applied directly.
The Two Pointer approach works because the greedy pointer-movement rule always eliminates dominated pairs.
Interview Explanation
A strong interview walkthrough:
1. Explain the area formula: min(height[left], height[right]) × width
2. Explain why the area is bottlenecked by the shorter line
3. Explain the greedy rule: always move the shorter pointer
4. Explain why moving the taller pointer cannot help
5. Walk through the dry run on the example
6. State O(n) time and O(1) space
7. Mention edge cases: equal heights, zeros, two elements
Interview Tips
Interviewers often ask:
- Why do you move the shorter pointer and not the taller one?
- What if both heights are equal?
- Why is the complexity O(n) and not O(n²)?
- Can the area ever increase after moving a pointer?
- How do you know no valid pair is missed?
- What is the area formula?
- Is this greedy or dynamic programming?
- Can this be extended to 3D containers?
- How do you handle integer overflow?
- What is the loop invariant?
Be prepared to explain the greedy insight before writing code.
Approach Comparison
| Approach | Time | Space | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Checks all pairs |
| Two Pointer | O(n) | O(1) | Optimal — greedy elimination |
Similar Problems
- Two Sum II — Two Pointer on a sorted array to find a target sum.
- Three Sum — Fix one element, apply Two Pointer for the remaining two.
- Trapping Rain Water — Related but requires tracking both left-max and right-max heights.
Container With Most Water and Trapping Rain Water are often confused. The key difference:
Container With Most Water → One rectangle spanning left to right
Trapping Rain Water → Sum of water above each bar between two walls
Unit Tests
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
class ContainerWithMostWaterTest {
final ContainerWithMostWater solution =
new ContainerWithMostWater();
@Test
void example1() {
assertThat(
solution.maxArea(
new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}))
.isEqualTo(49);
}
@Test
void example2() {
assertThat(
solution.maxArea(
new int[]{1, 1}))
.isEqualTo(1);
}
@Test
void symmetricTallEnds() {
assertThat(
solution.maxArea(
new int[]{4, 3, 2, 1, 4}))
.isEqualTo(16);
}
@Test
void allSameHeight() {
assertThat(
solution.maxArea(
new int[]{3, 3, 3, 3}))
.isEqualTo(9);
}
@Test
void allZeros() {
assertThat(
solution.maxArea(
new int[]{0, 0, 0}))
.isEqualTo(0);
}
@Test
void monotonicallyIncreasing() {
assertThat(
solution.maxArea(
new int[]{1, 2, 3, 4, 5}))
.isEqualTo(6);
}
@Test
void singleTallMiddleLine() {
assertThat(
solution.maxArea(
new int[]{1, 1000, 1}))
.isEqualTo(2);
}
@Test
void nullInputThrows() {
assertThrows(
NullPointerException.class,
() -> solution.maxArea(null));
}
@Test
void tooShortThrows() {
assertThrows(
IllegalArgumentException.class,
() -> solution.maxArea(new int[]{5}));
}
}
Summary
Container With Most Water is the canonical problem for the Two Pointer greedy pattern. The brute-force O(n²) approach checks all pairs but is too slow. The Two Pointer approach achieves O(n) time and O(1) space by exploiting the greedy insight that moving the shorter pointer is the only way to potentially increase the area. The algorithm is provably correct — every discarded pair is dominated by a pair already evaluated. Mastering this problem builds the intuition needed for Trapping Rain Water, Three Sum, and many other Two Pointer problems.
Key Takeaways
- The area formula is
min(height[left], height[right]) × (right - left). - The area is always limited by the shorter line.
- Always move the pointer at the shorter line inward.
- Moving the taller pointer cannot increase the area.
- When heights are equal, moving either pointer is valid.
- The Two Pointer approach is O(n) time and O(1) space.
- No valid pair is ever missed — dominated pairs are safely skipped.
- Use
left < rightto ensure a valid two-wall container. - Discuss integer overflow for large inputs.
- Distinguish this problem from Trapping Rain Water — different formula and logic.