LeetCode · #11

Container With Most Water Solution

Given n vertical lines, find two lines that together with the x-axis form a container holding the most water.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #11

🏗️

Pattern

Two Pointers — move shorter wall

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]). Find two lines that, together with the x-axis, form a container that holds the most water. Return the maximum amount of water.

Example

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

Constraints

 • n == height.length • 2 ≤ n ≤ 10⁵ • 0 ≤ height[i] ≤ 10⁴ 

Section Two · Approach 1

Brute Force — O(n²)

Try every pair of lines, compute the area for each, and track the maximum. The area formed by lines i and j is min(height[i], height[j]) × (j − i).

Problem: O(n²) pairs to check. The key insight is that moving the shorter wall inward is the only way to potentially find a larger area — moving the taller wall can never help because the area is limited by the shorter wall.

Java — Brute Force

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

Python — Brute Force

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

Metric	Value
Time	O(n²)
Space	O(1)

Section Three · Approach 2

Two Pointers — O(n)

Start with the widest container (pointers at both ends). Compute the area. Then move the pointer pointing to the shorter wall inward — because keeping the shorter wall and reducing width can only make things worse, but moving the shorter wall might find a taller one.

💡 Mental model: Imagine two walls of a swimming pool. Water level is limited by the shorter wall. If you slide the shorter wall inward, you lose width but might gain height — a worthwhile trade. Sliding the taller wall inward loses width AND can't gain height (still limited by the short wall) — always a loss.

Algorithm

Step 1: left = 0, right = n - 1, maxArea = 0.
Step 2: Compute area = min(height[left], height[right]) × (right − left).
Step 3: Update maxArea.
Step 4: Move the pointer with the smaller height inward.
Step 5: Repeat until pointers meet.

🎯 Why moving the shorter wall is correct:

The area is min(h_left, h_right) × width.
If h_left < h_right, then for every position j between left+1 and right, the pair (left, j) has area ≤ h_left × (j − left) < h_left × width — always smaller than the current area.
So we can safely discard left and move inward. The greedy choice eliminates all provably-suboptimal pairs.

Section Four · Trace

Visual Walkthrough

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

Two Pointers — move shorter wall inward

Section Five · Implementation

Code — Java & Python

Java — Two Pointers

 class Solution {
public int maxArea(int[] height) {
int left = 0, 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++; // move shorter wall else
right--;
        }
return maxArea;
    }
}

Python — Two Pointers

 class Solution:
def maxArea(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
max_area = 0 while left < right:
            area = min(height[left], height[right]) * (right - left)
            max_area = max(max_area, area)
if height[left] < height[right]:
                left += 1 else:
                right -= 1 return max_area

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(n²)	O(1)	Every pair; too slow for n = 10⁵
Two Pointers ← optimal	O(n)	O(1)	Greedy elimination of suboptimal pairs

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Two elements	`[1, 1]`	Only one pair. Area = min(1,1) × 1 = 1.
All same height	`[5, 5, 5, 5]`	Max area is at widest pair: 5 × 3 = 15.
Descending	`[5, 4, 3, 2, 1]`	Right pointer moves inward each time. Max is at start: min(5,1)×4=4 or min(5,2)×3=6...
Zero heights	`[0, 2, 0]`	Any pair with 0 has area 0. Only non-zero pairs matter.
Equal heights	`[3, 3]`	When heights are equal, either pointer can move — both discard symmetric candidates.

⚠ Common Mistake: Moving the taller wall instead of the shorter one. This is always wrong — moving the tall wall shrinks width while the height stays bottlenecked by the short wall. Only moving the short wall has any chance of increasing area.

← Back to Two Pointers problems

LearningTree

LC 11 · Container With Most Water — Solution & Explanation | DSA Guide