Difficulty Pattern Asked At LeetCode Link
Medium Two Pointers (Opposite Ends) Amazon, Google, Microsoft, Bloomberg, Apple leetcode.com/problems/container-with-most-water
📌 This is part of the Two Pointers series on Daily Dev Notes. If you haven’t read the Two Pointers pattern guide yet, start there — it will make this solution much easier to understand.
This problem has a sneaky quality to it.
When you first read it, it looks like a geometry problem. But once you see the right way to think about it, it becomes a clean, elegant Two Pointers problem that solves in a single pass.
The hard part is not the code — the code is just 10 lines. The hard part is building the intuition for why the Two Pointers approach is correct. That’s what this post focuses on.
Let’s go from scratch.
The Problem Statement
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 at (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 a container can store.
Note: You cannot slant the container.
Example
Example 1:
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
Why: Lines at index 1 (height=8) and index 8 (height=7)
Width = 8 - 1 = 7
Height = min(8, 7) = 7
Area = 7 × 7 = 49
Example 2:
Input: height = [1, 1]
Output: 1
Why: Only two lines. Width=1, Height=min(1,1)=1, Area=1
Understanding the Area Formula
Before jumping into the solution, let’s make sure the area calculation is completely clear.
If you pick two lines at positions i and j (where i < j), the water they can hold is:
Example
Area = width × height
= (j - i) × min(height[i], height[j])
The height is min() of the two lines because water spills
over the shorter one — you can never fill above the shorter line.
💡 The area is always limited by the SHORTER line. This single observation is the entire key to understanding why the Two Pointers approach works.
Step 1 — Brute Force Approach
As always, let’s start with the obvious solution. Check every possible pair of lines and track the maximum area.
Brute Force
// Brute Force — O(n²) time, O(1) space
int maxArea(vector& height) {
int maxWater = 0;
int n = height.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int width = j - i;
int h = min(height[i], height[j]);
int area = width * h;
maxWater = max(maxWater, area);
}
}
return maxWater;
}
Metric Brute Force Impact
Time Complexity O(n²) Two nested loops — for n=10,000, that’s 100 million operations
Space Complexity O(1) Fine — no extra data structures
LeetCode Result TLE Fails on large test cases — Time Limit Exceeded
⚠️ The brute force is logically correct but too slow. For n = 100,000 lines, it would need 10 billion comparisons. We need O(n).
Step 2 — Building the Intuition
This is the most important section. Read it slowly.
Let’s start with two pointers — one at the leftmost line (index 0) and one at the rightmost line (index n-1). This gives us the maximum possible width.
Now we calculate the area. Then we ask: should we move the left pointer or the right pointer?
🤔 Here is the key question: if we move one pointer inward, the WIDTH always decreases. So for the area to possibly increase, the HEIGHT must increase. Which pointer should we move to give the HEIGHT a chance to increase?
The Proof — Why We Always Move the Shorter Line
Say the left line has height 3 and the right line has height 8. The current area is limited by height 3 (the shorter one).
What if we move the RIGHT pointer (height 8) inward?
Width decreases Always — we moved inward
New right line height Could be anything — but the area is STILL limited by left line (height 3)
Can area increase? NO — width went down, height is still capped at 3. Area can only stay same or decrease.
What if we move the LEFT pointer (height 3) inward?
Width decreases Always — we moved inward
New left line height Could be greater than 3 — this is our only chance for area to increase
Can area increase? YES — if the new left height is greater than 3, the effective height increases and might outweigh the width decrease
🔑 CONCLUSION: Always move the pointer pointing to the SHORTER line. Moving the taller line’s pointer can never increase the area. Moving the shorter line’s pointer is the only move that gives us a chance at a larger area.
This is the entire algorithm. Everything else — the code, the loop — is just implementing this one insight.
Step 3 — Full Dry Run
Let’s trace through Example 1 completely.
Dry Run
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
index = [0, 1, 2, 3, 4, 5, 6, 7, 8]
maxArea = 0
Step left right h[left] h[right] Width Height Area maxArea Move
1 0 8 1 7 8 1 8 8 left++ (1 < 7)
2 1 8 8 7 7 7 49 49 right– (8 > 7)
3 1 7 8 3 6 3 18 49 right– (8 > 3)
4 1 6 8 8 5 8 40 49 right– (tie → move right)
5 1 5 8 4 4 4 16 49 right– (8 > 4)
6 1 4 8 5 3 5 15 49 right– (8 > 5)
7 1 3 8 2 2 2 4 49 right– (8 > 2)
8 1 2 8 6 1 6 6 49 right– (8 > 6)
9 1 1 – – – – – 49 left >= right → STOP
✅ Maximum area = 49. Found at Step 2: lines at index 1 (height=8) and index 8 (height=7). Width=7, Height=7, Area=49.
Notice something important in Step 4: when both lines have the same height (both are 8), we can move either pointer — it doesn’t matter. Moving either one cannot increase the area since height stays capped at 8 and width decreases.
READ FULL ARTICLE: https://dailydevnotes.in/leetcode-11-container-with-most-water/
Top comments (0)