SyntaxPilot
Courses/DSA and Coding Problems/Lesson 7
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 7 of 90

Container With Most Water

queued

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

  1. Start with the widest pair, l = 0 and r = n - 1. No pair is wider.
  2. Every other pair is narrower, so to beat the current one we need a higher water level.
  3. 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.
  4. So move the shorter wall. It is the only move that might find a taller partner.
  5. 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] (because l is 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

  1. 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].

  1. 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.

  1. 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.

  1. 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

  1. 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.
  2. 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.
  3. Is this greedy or two pointers? Both: a greedy rule (discard the shorter wall) carried out with two pointers.
  4. Time and space? O(n) time, O(1) space.
  5. 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).