Frequently Asked at Google — This problem has been reported multiple times in recent Google L4 interviews.

Container With Most Water (LC 11)

Problem Statement

Given an integer array height where height[i] is the height of the i-th vertical line at position i, find two lines that together with the x-axis form a container holding the most water. Return the maximum area.

Example 1:

Input:  height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The lines at i=1 (height 8) and i=8 (height 7) form a container of area min(8,7)*(8-1)=49.

Example 2:

Input:  height = [1,1]
Output: 1

Constraints:

• 2 <= height.length <= 10^5
• 0 <= height[i] <= 10^4

Difficulty: Medium

---

Pattern Recognition

• Input structure: 1D array of heights.
• What are we maximizing? area = min(h[i], h[j]) * (j - i).
• Pattern: two pointers (greedy).
• Why: the area depends on the shorter of the two lines and the distance. Starting wide and narrowing always removes the shorter line first — because keeping it can only reduce the width without increasing the bounded height.

---

Approach

Brute Force

Try every pair (i, j). O(n^2) time. TLE at n = 10^5.

Optimal — Two Pointers

Key Insight: Starting from the widest possible container, the area is capped by the shorter side. Moving the taller side inward cannot help — you still have the same short bound but less width. So always move the shorter side inward; it is the only move that might produce a taller bound.

1. left = 0, right = n - 1, best = 0.
2. While left < right:
   • area = min(height[left], height[right]) * (right - left).
   • Update best.
   • If height[left] < height[right], left++; else right--.
3. Return best.

Time: O(n) — each pointer moves at most n times. Space: O(1).

Why it's correct (formal): At any step, the pair (left, right) with the shorter side being discarded cannot be part of the optimal answer. Reason: any container that includes this shorter side pairs it with some other line; the width with that other line is at most right - left (since we are currently at the max-width configuration), and the height is bounded by the shorter side. So the area of any such container is ≤ the current area. Discarding is safe.

---

Walkthrough

height = [1,8,6,2,5,4,8,3,7].

left	right	h[l]	h[r]	area	best	move
0	8	1	7	min(1,7)*8=8	8	l++ (h[l] smaller)
1	8	8	7	min(8,7)*7=49	49	r--
1	7	8	3	3*6=18	49	r--
1	6	8	8	8*5=40	49	r-- (or l++)
1	5	8	4	4*4=16	49	r--
1	4	8	5	5*3=15	49	r--
1	3	8	2	2*2=4	49	r--
1	2	8	6	6*1=6	49	r--
1	1	stop

Answer: 49.

---

Implementation

TypeScript

function maxArea(height: number[]): number {
    let left = 0;
    let right = height.length - 1;
    let best = 0;
    while (left < right) {
        const width = right - left;
        const h = Math.min(height[left], height[right]);
        best = Math.max(best, width * h);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return best;
}

C++

int maxArea(vector<int>& height) {
    int left = 0, right = (int)height.size() - 1;
    int best = 0;
    while (left < right) {
        int width = right - left;
        int h = min(height[left], height[right]);
        best = max(best, width * h);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return best;
}

Watch out:

1. Using <= in while (left <= right) counts a zero-width container; always use <.
2. Moving the taller side (or both) breaks correctness. The invariant requires moving the shorter side.
3. With equal heights, either move is safe — pick one consistently to simplify reasoning.

---

Complexity Analysis

	Time	Space
Brute Force	O(n^2)	O(1)
Two Pointers	O(n)	O(1)

Bottleneck: you must look at every height at least once. O(n) is tight because the two pointers collectively make n-1 moves.

---

Edge Cases

1. Two elements — n=2, one pair. Your loop handles it.
2. All zeros — area always 0. Good sanity check.
3. Monotonically increasing heights — optimal pair is near the right end. Pointers migrate from left.
4. Monotonically decreasing — symmetric.
5. One extremely tall line — it acts as a cap only when the other side is short; correctness hinges on moving the short side.
6. Duplicates of the max height — any pair of those maxes on opposite sides is the answer.

---

Related Problems

• LC 42 — Trapping Rain Water — Similar two-pointer strategy, different objective (volume trapped between bars).
• LC 84 — Largest Rectangle in Histogram — Different pattern (monotonic stack), but often brought up in the same follow-up sequence.
• LC 16 — 3Sum Closest — Two-pointer after sorting; same pointer-collapsing logic.
• LC 1793 — Maximum Score of a Good Subarray — Two-pointer variant where you expand outward from a fixed index.

---

What Is Expected at Each Level

Junior: Get to brute force, then two-pointer with a hint. State time complexity correctly.

Mid-level: Two-pointer on first try, explain the invariant crisply, correctly handle the equal-height tie-break.

Senior (L4 target): Prove correctness in words (the "discarding the shorter side never sacrifices a better answer" argument), contrast with Trapping Rain Water so the interviewer sees you understand why the greedy works. Discuss extensions — e.g., three lines forming a container — and why the two-pointer trick does not generalize.