These are the notes for DSA episode 7. Container With Most Water (LeetCode 11) asks which two walls hold the most water. Trying every pair is O(n²). The two-pointer solution starts with the widest pair and always moves the shorter wall inward, for O(n) time and O(1) space. The code is short; the important part is the proof that this greedy move never skips the answer. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
Ramesh, a farmer, has a row of old walls on his land, one metre apart, all different heights. Before the monsoon he wants to pick two walls, seal the ground and the sides between them, and store rainwater. Which two walls hold the most water?
The shorter wall decides
Think of a bucket with one broken, short side: fill it, and the water spills over the short side, however tall the others are. Between two walls:
water level = min(h[l], h[r]) (the shorter wall)
width = r - l (the distance between them)
water = min(h[l], h[r]) * (r - l)
Problem statement
Given n non-negative heights h, choose l < r to maximize min(h[l], h[r]) * (r - l). The walls in between don't block anything in this problem. Constraints: 2 ≤ n ≤ 10⁵, 0 ≤ h[i] ≤ 10⁴.
| h | answer | best pair |
|---|---|---|
| [1, 8, 6, 2, 5, 4, 8, 3, 7] | 49 | walls 1 and 8: min(8, 7) × 7 |
| [1, 1] | 1 | the only pair |
| [4, 3, 2, 1, 4] | 16 | the two ends: 4 × 4 |
| [1, 2, 1] | 2 | the two ends: 1 × 2 |
Brute force: every pair
public class Main {
static int maxArea(int[] h) {
int best = 0;
for (int i = 0; i < h.length; i++)
for (int j = i + 1; j < h.length; j++)
best = Math.max(best, Math.min(h[i], h[j]) * (j - i));
return best;
}
public static void main(String[] args) {
System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
}
}
Output:
49
On ten lakh walls:
int n = 1000000, h[] = new int[n];
for (int i = 0; i < n; i++) h[i] = (int) (i * 7919L % 1000) + 1;
System.out.println(maxArea(h));
Result: Time Limit Exceeded. There are n(n-1)/2 pairs, about 5 × 10¹¹ for a million walls: O(n²).
The key insight: start wide, then squeeze
- Start with the widest pair,
l = 0andr = n - 1. No pair is wider. - Every other pair is narrower, so to beat the current one we need a higher water level.
- Moving the taller wall inward: the level is still capped by the shorter wall (which didn't move), and the width shrinks. It can never be better.
- So move the shorter wall. It is the only move that might find a taller partner.
- One pointer moves each step, so after at most n - 1 steps they meet: O(n).
The proof (interviewers ask for it)
Say h[l] < h[r]. Moving l skips exactly the pairs (l, r-1), (l, r-2), ..., (l, l+1). Each of them:
- has a level of at most
h[l](becauselis in the pair), and - is narrower than
(l, r).
So each holds at most h[l] × (r - l), which we have already recorded. Wall l can't be part of any better answer, and discarding it loses nothing. When h[l] == h[r], the same argument works for either wall, so moving either one is safe.
Dry run: [1, 8, 6, 2, 5, 4, 8, 3, 7]
| l (h) | r (h) | water | best | move |
|---|---|---|---|---|
| 0 (1) | 8 (7) | 1 × 8 = 8 | 8 | l is shorter: l++ |
| 1 (8) | 8 (7) | 7 × 7 = 49 | 49 | r is shorter: r-- |
| 1 (8) | 7 (3) | 3 × 6 = 18 | 49 | r-- |
| 1 (8) | 6 (8) | 8 × 5 = 40 | 49 | equal: r-- |
| 1 (8) | 5 (4) | 4 × 4 = 16 | 49 | r-- |
| 1 (8) | 4 (5) | 5 × 3 = 15 | 49 | r-- |
| 1 (8) | 3 (2) | 2 × 2 = 4 | 49 | r-- |
| 1 (8) | 2 (6) | 6 × 1 = 6 | 49 | r--, pointers meet |
Answer: 49, in 8 steps instead of 36 pairs.
The optimal solution
public class Main {
static int maxArea(int[] h) {
int l = 0, r = h.length - 1, best = 0;
while (l < r) {
int area = Math.min(h[l], h[r]) * (r - l);
best = Math.max(best, area);
if (h[l] < h[r]) l++;
else r--;
}
return best;
}
public static void main(String[] args) {
System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
System.out.println(maxArea(new int[]{1, 1}));
System.out.println(maxArea(new int[]{4, 3, 2, 1, 4}));
System.out.println(maxArea(new int[]{1, 2, 1}));
}
}
Output:
49
1
16
2
On the ten lakh walls that timed out:
long t = System.nanoTime();
int ans = maxArea(h);
System.out.println(ans + " " + (System.nanoTime() - t) / 1000000 + " ms");
Output (the time varies from run to run):
999000000 8 ms
The same solution in C++ and Python
#include <bits/stdc++.h>
using namespace std;
int maxArea(const vector<int>& h) {
int l = 0, r = h.size() - 1, best = 0;
while (l < r) {
best = max(best, min(h[l], h[r]) * (r - l));
if (h[l] < h[r]) l++;
else r--;
}
return best;
}
int main() {
cout << maxArea({1, 8, 6, 2, 5, 4, 8, 3, 7}) << "\n"; // 49
cout << maxArea({4, 3, 2, 1, 4}) << "\n"; // 16
}
def max_area(h):
l, r, best = 0, len(h) - 1, 0
while l < r:
best = max(best, min(h[l], h[r]) * (r - l))
if h[l] < h[r]:
l += 1
else:
r -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49
print(max_area([4, 3, 2, 1, 4])) # 16
Complexity
| Approach | Time | Extra space | n = 10⁶ |
|---|---|---|---|
| Every pair | O(n²) | O(1) | Time Limit Exceeded |
| Two pointers (move the shorter wall) | O(n) | O(1) | milliseconds |
Unlike 3Sum, there is no sorting: the walls must stay where they are, because the width depends on their positions.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
if (h[l] > h[r]) l++; (move the taller wall) |
8 (answer is 49) |
discards the tall walls that make the answer | move the shorter wall |
Math.max(h[l], h[r]) |
56 (answer is 49) |
water would stand above the short wall | Math.min(h[l], h[r]) |
width r - l + 1 |
56 (answer is 49) |
counts walls instead of the gaps between them | width = r - l |
while (l <= r) |
one extra step with width 0 | pairs a wall with itself | while (l < r) |
int area when heights and n are both huge |
overflow past 2,147,483,647 | 10⁵ walls × 10⁴ height fits; 10⁶ × 10⁴ does not | use long for bigger limits |
Mini project: Ramesh's tank planner
Print which two walls give the answer and how many litres that is, if each unit is 1,000 litres. Track bestL and bestR whenever best improves. For [1, 8, 6, 2, 5, 4, 8, 3, 7] the program in the video prints 1 and 8: 49000 litres and Steps: 8, pairs: 36.
Practice
- Prove that when
h[l] == h[r], moving either pointer is safe.
Solution
Every skipped pair using l has level ≤ h[l] and is narrower than (l, r), so it is no better than h[l] × (r - l), which is already recorded. The same holds for r because h[r] = h[l].
- Answer for
[2, 3, 4, 5, 18, 17, 6].
Solution
17: walls 4 and 5 give min(18, 17) × 1 = 17. The ends give min(2, 6) × 6 = 12, and walls 1 and 6 give min(3, 6) × 5 = 15.
- Boats to Save People (LeetCode 881): people weigh
[3, 2, 2, 1], a boat carries at most 2 people and weight 3. Minimum boats?
Solution
Sort, two pointers: if the lightest and heaviest fit together, both go; otherwise the heaviest goes alone. [1, 2, 2, 3]: 3 alone, 1 + 2, 2 alone → 3 boats.
- Valid Palindrome with two pointers: is
"A man, a plan, a canal: Panama"a palindrome, ignoring non-letters and case?
Solution
Pointers at both ends, skip characters that aren't letters or digits, compare lowercase versions, move inward. Answer: true.
Quick quiz
What does maxArea(new int[]{2, 3, 10, 5, 7, 8, 9}) return?
- 36
- 18
- 40
- 45
Answer
36. Walls 2 (height 10) and 6 (height 9): min(10, 9) × 4 = 36. The ends only give min(2, 9) × 6 = 12.
Interview questions
- Why start with the widest pair? It is the only pair with the maximum width; every move after it trades width for a possibly higher level.
- Why is moving the taller wall never useful? The level stays capped by the shorter wall, and the width shrinks, so the area can only fall or stay the same.
- Is this greedy or two pointers? Both: a greedy rule (discard the shorter wall) carried out with two pointers.
- Time and space? O(n) time, O(1) space.
- How is this different from Trapping Rain Water? Here you pick one pair and the middle walls don't matter. In Trapping Rain Water every dip fills, and the walls in between block water.
Glossary
| Term | Meaning |
|---|---|
| Container | The space between two chosen walls |
| Water level | The height of the shorter of the two walls |
| Width | The distance between the walls, r - l |
| Area | Level × width, the water held |
| Two pointers | Two indexes, here starting at both ends and moving inward |
| Greedy algorithm | An algorithm that makes the locally best choice at each step |
| Proof of correctness | An argument showing an algorithm never misses the right answer |
| Overflow | A result too big for its type, which wraps around to a wrong value |
Summary
- Two walls hold
min(h[l], h[r]) × (r - l); every pair is O(n²). - Start with the widest pair; moving the taller wall can never help, so move the shorter one.
- The proof: every pair you skip is narrower and no higher than one you already measured.
- O(n) time, O(1) space.
Next episode: Trapping Rain Water (hard).