What if the best answer is hiding at the two ends?
At first glance, Container With Most Water looks like a problem where we need to try every possible pair of lines.
There are potentially thousands or even millions of pairs. So the obvious solution quickly becomes too slow.
But there is a simple observation that lets us eliminate huge numbers of possibilities without checking them.
The trick is a classic Two Pointer technique.
1. The Problem
You are given an integer array height.
Each element represents the height of a vertical line.
The line at index i and the line at index j can form a container.
The goal is to find the pair of lines that can hold the maximum amount of water.
The amount of water between two lines is determined by two things:
- The distance between the two lines.
- The height of the shorter line.
Area = min(height[i], height[j]) × (j - i)
For example, if two lines have heights 8 and 5,
and they are 4 positions apart:
Area = min(8, 5) × 4 = 5 × 4 = 20
2. Naive Thinking: Try Every Pair
The first idea that naturally comes to mind is:
- Pick every possible left line.
- Pick every possible right line.
- Calculate the area.
- Keep track of the maximum.
That means checking every pair:
for (let i = 0; i < height.length; i++) {
for (let j = i + 1; j < height.length; j++) {
// calculate area
}
}
If the array contains n elements, there can be roughly
n² pairs.
Therefore, the brute-force approach has:
Time Complexity: O(n²)
That is the part we need to improve.
3. The Key Insight: The Shorter Line Controls the Water
This is the most important observation in the problem.
Consider two lines:
Left = 3
Right = 7
Even though the right line is height 7, the container can only hold water
up to height 3.
So the area is:
min(3, 7) × width
Now suppose we move the taller line.
The width becomes smaller, but the limiting height is still potentially
3.
So moving the taller line cannot give us a better answer while the shorter line remains unchanged.
The Rule
Always move the pointer pointing to the shorter line.
This single observation reduces the problem from O(n²) to O(n).
4. Visual Walkthrough
Let's imagine the array:
Index: 0 1 2 3 4 5 6 7
Height: 1 8 6 2 5 4 8 3
We start with two pointers:
i = 0
j = 7
The two heights are:
height[i] = 1
height[j] = 3
width = 7
Therefore:
Area = min(1, 3) × 7 = 7
The shorter line is at i, so we move i forward.
i → 1
j → 7
Now:
height[i] = 8
height[j] = 3
width = 6
Area = min(8, 3) × 6
= 18
The shorter line is now at j, so we move j backward.
We continue this process until the two pointers meet.
Why don't we miss the answer?
Suppose the left line is shorter. Keeping that same left line and moving the right pointer inward can only reduce the width.
Since the left line is already limiting the height, those possibilities cannot produce a better container than the current pair.
Therefore, we can safely discard that shorter line and move its pointer.
5. Your JavaScript Solution
Here is the two-pointer implementation:
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
let area = 0
let i = 0; j = height.length - 1
while (i < j) {
if (height[i] > height[j]) {
area = Math.max(area, height[j] * (j - i));
j--
} else {
area = Math.max(area, height[i] * (j - i));
i++
}
}
return area
};How the Code Works
We initialize two pointers:
let i = 0;
let j = height.length - 1;One pointer starts at the beginning and the other starts at the end.
Then we repeatedly calculate the current container area:
height[shorterPointer] * (j - i)If the left line is taller than the right line:
j--Otherwise, we move the left pointer:
i++Notice that your implementation handles equal heights by moving the left pointer. This is completely valid because either pointer can be moved when both heights are equal.
6. Edge Cases
Case 1: Two Elements
If there are only two lines, there is only one possible container.
[5, 8]
Area = min(5, 8) × 1
= 5Case 2: All Heights Are Equal
[5, 5, 5, 5]
The algorithm still works normally. When both heights are equal,
the else branch moves the left pointer.
Case 3: Increasing Heights
[1, 2, 3, 4, 5]The algorithm starts from both ends and keeps moving the shorter pointer. No nested loops are required.
Case 4: Very Large Input
This is where the two-pointer solution really matters. Instead of checking every pair, each pointer moves across the array only once.
7. Complexity Analysis
| Metric | Complexity |
|---|---|
| Time | O(n) |
| Space | O(1) |
Why O(n)?
Both pointers only move toward each other. The left pointer never moves backward, and the right pointer never moves forward.
Therefore, across the entire algorithm, there are at most n pointer
movements.
The algorithm also uses only a few variables, so the extra space is O(1).
8. How to Explain This in an Interview
If you get this problem in an interview, avoid immediately jumping into code. Explain the reasoning first.
Step 1: The area between two lines is determined by the shorter line and the distance between them.
Step 2: Start with pointers at both ends to maximize the initial width.
Step 3: Calculate the current area and update the maximum.
Step 4: Move the pointer pointing to the shorter line because keeping that line while reducing the width cannot produce a better result.
Step 5: Continue until the pointers meet.
A concise interview explanation could be:
I use two pointers starting from both ends. For every pair, the shorter height limits the amount of water, while the distance gives the width. After calculating the area, I move the pointer at the shorter height because moving the taller pointer would only decrease the width without increasing the limiting height. This allows us to eliminate impossible candidates and solve the problem in O(n) time and O(1) space.
9. The Reusable Pattern: Two Pointers
The most valuable thing about this problem isn't memorizing the solution. It's recognizing the pattern.
The Two Pointer technique is useful when:
- You are working with an array or string.
- You need to compare elements from opposite sides.
- The search space can be reduced based on a condition.
- Moving one pointer allows you to safely eliminate possibilities.
The general structure looks like this:
let left = 0;
let right = arr.length - 1;
while (left < right) {
// calculate / evaluate current state
if (some_condition) {
left++;
} else {
right--;
}
}The important question to ask yourself when you see a similar problem is:
"Can I eliminate an entire set of possibilities by moving one pointer?"
If the answer is yes, there is a good chance a two-pointer solution can turn a quadratic approach into a linear one.
10. Conclusion
Container With Most Water is a great example of how an algorithmic insight can completely change the performance of a solution.
The brute-force approach checks every possible pair and takes O(n²). The two-pointer approach intelligently eliminates impossible candidates and brings the complexity down to O(n).
The key idea to remember is simple:
Find the shorter line → calculate area → move the shorter pointer.
Once this reasoning becomes familiar, you'll start seeing the same pattern in many other array and string problems.
Don't just remember the code. Remember why moving the shorter pointer is safe. That's the real solution.
