Topics › Sliding Window and Two Pointers › Medium Problems

Container with most water

Easy TUF ID 2396 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array height of n non-negative integers. Picture n vertical lines at x-positions 0, 1, ..., n - 1, where line i goes from (i, 0) up to (i, height[i]). Choose two lines i < j. Together with the x-axis they form a container that holds

water(i, j) = min(height[i], height[j]) × (j - i)

because the water level cannot rise above the shorter line. Return the maximum water any pair can hold. The lines between i and j do not matter; the container is just the two walls.

Constraints (LeetCode 11): 2 ≤ n ≤ 10^5, 0 ≤ height[i] ≤ 10^4. The methods return long so they stay correct even for heights up to Integer.MAX_VALUE, and they return 0 when fewer than two lines exist.

Example 1

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
answer = 49         // lines at x = 1 (height 8) and x = 8 (height 7): min(8, 7) × 7

Example 2

height = [4, 3, 2, 1, 4]
answer = 16         // the two outer lines: min(4, 4) × 4

Do not confuse this with “Trapping Rain Water”, where every bar holds water above it and the bars in between matter. Here only two lines are chosen and the rest are ignored.

Approach 1: Brute force

Intuition. Every container is a pair of lines, so evaluate every pair and keep the best. Starting j at i + 1 covers each pair exactly once.

Algorithm.

1. For every i, for every j > i: compute min(height[i], height[j]) × (j - i).
2. Track the maximum.

static long bruteForce(int[] height) {
    long best = 0;
    for (int i = 0; i < height.length; i++) {
        for (int j = i + 1; j < height.length; j++) {
            long area = (long) Math.min(height[i], height[j]) * (j - i);
            best = Math.max(best, area);
        }
    }
    return best;
}

Complexity. Time O(n^2): n(n - 1)/2 pairs. Space O(1).

For n = 10^5 that is about 5 × 10^9 pairs. We need a way to rule out most pairs without evaluating them.

Approach 2: Optimal, two pointers

Intuition. Start with the widest possible container: i = 0 and j = n - 1. Every other container is narrower, so the only way to beat the current one is with a taller limiting line. Now look at the shorter of the two lines, say height[i] ≤ height[j]. Pair line i with any other partner k between them (i < k < j):

• the width k - i is smaller than j - i, and
• the height min(height[i], height[k]) is at most height[i].

So every container that uses line i with a closer partner is no better than the one we just measured. Line i has nothing left to offer, and we can discard it by moving i one step right. Symmetrically, if height[j] is the shorter, discard j. Each step discards one line for good, so after at most n - 1 steps the pointers meet.

Moving the taller line instead would be a mistake: the shorter line stays as the limit, the width shrinks, and the area can only go down, while we might throw away the taller line’s best partner.

Algorithm.

1. i = 0, j = n - 1, best = 0.
2. While i < j:
   • best = max(best, min(height[i], height[j]) × (j - i)).
   • If height[i] < height[j], do i++; otherwise do j--.
3. Return best.

static long optimal(int[] height) {
    long best = 0;
    int i = 0, j = height.length - 1;
    while (i < j) {
        long area = (long) Math.min(height[i], height[j]) * (j - i);
        best = Math.max(best, area);
        if (height[i] < height[j]) i++;                  // the shorter line cannot do better with any closer partner
        else j--;
    }
    return best;
}

Dry run on Example 1, height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

Complexity. Time O(n): each iteration moves one pointer inward by one. Space O(1).

Why the pruning never loses the optimum. Let (a, b) be an optimal pair with a positive amount of water (if the best is 0, returning 0 is already right). The algorithm measures (a, b) unless it discards a or b first. Suppose the left pointer sits on a while the right pointer is at some j > b. The algorithm would discard a only if height[a] < height[j]. But then the pair (a, j) has height height[a] ≥ min(height[a], height[b]) and width j - a > b - a, so it holds strictly more water than (a, b), which contradicts optimality. So a survives until the right pointer comes down to b. The mirror argument shows b survives while the left pointer moves up to a. Therefore the pointers eventually sit on a and b at the same time, and the optimum is measured.

Edge cases and pitfalls

• Fewer than two lines. No container exists; both methods return 0 because the loops do not run.
• Zero heights. A zero-height line holds no water with any partner. [0, 0] returns 0.
• Equal heights. When height[i] == height[j], moving either pointer is safe: neither line can do better with a closer partner, because the other one of the pair already limits it. The code moves j.
• Best pair in the middle. [2, 3, 10, 5, 7, 8, 9] has its best container between 10 and 9 (area 36), not at the outer edges. The pointer moves walk past the short outer lines to find it.
• Overflow. min(height) × width can exceed int when heights are large. The code casts to long before multiplying; [10^9, 1, 10^9] gives 2 × 10^9.
• Confusing with Trapping Rain Water. Here intermediate lines are ignored entirely; there they hold water and the answer is a sum, not a maximum.

Related problems

• Trapping Rainwater also moves the pointer at the shorter side inward, for a related but different reason.
• Two Sum uses inward two pointers on a sorted array, discarding one element per step.
• 3 Sum runs the same inward sweep inside a loop over a fixed element.
• Kadane’s Algorithm, maximum subarray sum is the previous Blind 75 array problem.