LeetCode 11 - Container With Most Water

The problem gives an array called height, where each element represents the height of a vertical line drawn on a coordinate plane. The line at index i starts at (i, 0) and ends at (i, height[i]).

leetcodemediumarraytwo-pointersgreedy

LeetCode Problem 11

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy

Solution

Problem Understanding

The problem gives an array called height, where each element represents the height of a vertical line drawn on a coordinate plane. The line at index i starts at (i, 0) and ends at (i, height[i]).

We want to choose two different lines that, together with the x-axis, form a container capable of holding water. The amount of water the container can hold depends on two things:

  • The width between the two lines
  • The height of the shorter line

If we choose lines at positions left and right, then:

  • Width = right - left
  • Height = min(height[left], height[right])

So the area of water stored is:

$$\text{area} = (right - left) \times \min(height[left], height[right])$$

The task is to return the maximum possible area among all pairs of lines.

The constraints are important here:

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

Since the array can contain up to one hundred thousand elements, any solution worse than roughly linear or near-linear time will likely be too slow. A quadratic solution would require checking billions of pairs in the worst case, which is not practical.

Several edge cases are worth considering immediately:

  • Arrays with only two elements
  • Heights containing zeros
  • Strictly increasing or strictly decreasing heights
  • Multiple lines with the same height
  • Very tall lines placed close together versus shorter lines placed far apart

The problem guarantees at least two lines, so we never need to handle an empty array or a single-element array.

Approaches

Brute Force Approach

The most direct approach is to examine every possible pair of lines.

For every index i, we try every index j > i. For each pair, we compute:

$$(j - i) \times \min(height[i], height[j])$$

We keep track of the largest area encountered.

This approach is guaranteed to work because it explicitly checks all possible containers. Since the optimal answer must come from one of these pairs, exhaustive search eventually finds it.

The problem is efficiency. There are approximately:

$$\frac{n(n-1)}{2}$$

possible pairs.

With n = 10^5, this becomes far too large. The time complexity is O(n^2), which is not acceptable for the given constraints.

Optimal Two-Pointer Approach

The key observation is that the area depends on both width and the shorter height.

Suppose we start with the widest possible container by placing one pointer at the beginning and one at the end of the array.

At each step:

  • We calculate the current area.
  • Then we move the pointer pointing to the shorter line inward.

Why move the shorter line?

Because the shorter line is the limiting factor for the height of the container. Moving the taller line inward cannot increase the height limit, but it definitely decreases the width. That means the area cannot improve by moving the taller pointer while keeping the shorter one fixed.

By moving the shorter pointer, we give ourselves a chance to find a taller line that might compensate for the reduced width.

This greedy insight allows us to eliminate many impossible candidates without checking them individually.

The result is a linear-time solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every possible pair of lines
Optimal O(n) O(1) Uses two pointers and greedy elimination

Algorithm Walkthrough

  1. Initialize two pointers:
  • left = 0
  • right = len(height) - 1

These pointers represent the current pair of lines being considered. Starting at the extremes gives the maximum possible width. 2. Initialize a variable max_area = 0.

This variable stores the best answer found so far. 3. While left < right, compute the current container area.

The width is:

$$right - left$$

The usable height is:

$$\min(height[left], height[right])$$

Multiply them to get the current area. 4. Update max_area if the current area is larger.

This ensures we always keep track of the best container seen so far. 5. Move the pointer corresponding to the shorter line inward.

If height[left] < height[right], increment left.

Otherwise, decrement right.

This step is the heart of the algorithm. Since the shorter line limits the current area, keeping it while reducing width cannot produce a better result. 6. Continue until the two pointers meet.

Once left >= right, all meaningful pairs have been considered or safely eliminated. 7. Return max_area.

Why it works

The algorithm relies on an important invariant:

At every step, moving the taller pointer cannot improve the area because the shorter line already limits the height. Since moving either pointer reduces the width, the only possibility for improvement is finding a taller shorter line.

By always discarding the shorter line, we eliminate pairs that cannot possibly produce a better answer. This guarantees that the optimal solution is never skipped.

Python Solution

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1

        max_area = 0

        while left < right:
            width = right - left
            current_height = min(height[left], height[right])

            area = width * current_height
            max_area = max(max_area, area)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

The implementation follows the two-pointer strategy directly.

The variables left and right track the current boundaries of the container. Initially, they point to the widest possible pair.

Inside the loop, the code computes:

  • The width between the pointers
  • The limiting height using min
  • The resulting area

The maximum area seen so far is updated after each computation.

The key decision comes afterward. If the left height is smaller, the left pointer moves inward. Otherwise, the right pointer moves inward. This follows the greedy observation that only replacing the shorter boundary can potentially improve the result.

The loop stops when the pointers meet, because no valid container exists beyond that point.

Go Solution

func maxArea(height []int) int {
    left := 0
    right := len(height) - 1

    maxArea := 0

    for left < right {
        width := right - left

        currentHeight := height[left]
        if height[right] < currentHeight {
            currentHeight = height[right]
        }

        area := width * currentHeight

        if area > maxArea {
            maxArea = area
        }

        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }

    return maxArea
}

The Go implementation mirrors the Python solution closely.

Since Go does not provide built-in min and max functions for integers in older standard library versions, the comparisons are written explicitly using if statements.

The solution uses only integer arithmetic, and overflow is not a concern under the given constraints because the maximum area is:

$$10^5 \times 10^4 = 10^9$$

which fits safely within Go's standard int type on modern systems.

Slices in Go behave similarly to dynamic arrays, so accessing elements is straightforward.

Worked Examples

Example 1

Input:

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

Initial state:

  • left = 0
  • right = 8
Step left right height[left] height[right] Width Min Height Area Max Area Move
1 0 8 1 7 8 1 8 8 left++
2 1 8 8 7 7 7 49 49 right--
3 1 7 8 3 6 3 18 49 right--
4 1 6 8 8 5 8 40 49 right--
5 1 5 8 4 4 4 16 49 right--
6 1 4 8 5 3 5 15 49 right--
7 1 3 8 2 2 2 4 49 right--
8 1 2 8 6 1 6 6 49 right--

Pointers meet, algorithm stops.

Final answer:

49

The optimal container comes from indices 1 and 8:

  • Width = 8 - 1 = 7
  • Height = min(8, 7) = 7
  • Area = 7 * 7 = 49

Example 2

Input:

height = [1,1]
Step left right height[left] height[right] Width Min Height Area Max Area
1 0 1 1 1 1 1 1 1

Pointers meet immediately afterward.

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each pointer moves at most n times
Space O(1) Only a few variables are used

The two-pointer algorithm is linear because each iteration moves exactly one pointer inward. Since the pointers never move backward, the total number of iterations is at most n.

The algorithm uses constant extra space because it stores only a few integer variables regardless of input size.

Test Cases

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1

        max_area = 0

        while left < right:
            width = right - left
            current_height = min(height[left], height[right])

            area = width * current_height
            max_area = max(max_area, area)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

solution = Solution()

assert solution.maxArea([1,8,6,2,5,4,8,3,7]) == 49  # standard example
assert solution.maxArea([1,1]) == 1  # minimum valid size
assert solution.maxArea([4,3,2,1,4]) == 16  # equal tall boundaries
assert solution.maxArea([1,2,1]) == 2  # small symmetric case
assert solution.maxArea([0,0]) == 0  # all zero heights
assert solution.maxArea([0,2]) == 0  # one side zero
assert solution.maxArea([1,2,3,4,5]) == 6  # strictly increasing
assert solution.maxArea([5,4,3,2,1]) == 6  # strictly decreasing
assert solution.maxArea([2,3,10,5,7,8,9]) == 36  # optimal inside array
assert solution.maxArea([1,1000,1000,1]) == 1000  # large equal middle heights
assert solution.maxArea([10000,10000]) == 10000  # maximum height values

Test Summary

Test Why
[1,8,6,2,5,4,8,3,7] Standard reference example
[1,1] Smallest valid input
[4,3,2,1,4] Best container uses outer boundaries
[1,2,1] Symmetric small array
[0,0] All heights zero
[0,2] One boundary has zero height
[1,2,3,4,5] Strictly increasing heights
[5,4,3,2,1] Strictly decreasing heights
[2,3,10,5,7,8,9] Optimal pair is not at extremes
[1,1000,1000,1] Large equal internal heights
[10000,10000] Maximum height boundary values

Edge Cases

One important edge case is the smallest possible input size, where the array contains exactly two elements. In this situation, there is only one possible container. Some implementations accidentally assume multiple iterations or extra movement logic. The current solution handles this naturally because the loop executes once, computes the area, and terminates correctly.

Another important case involves heights containing zeros. A line of height zero cannot contribute to holding water because the minimum height becomes zero. Incorrect implementations sometimes overlook this and produce negative or invalid calculations. Here, the formula works correctly because multiplying by zero naturally gives an area of zero.

Strictly increasing or strictly decreasing arrays can also expose pointer movement bugs. For example, in [1,2,3,4,5], the algorithm repeatedly moves the smaller pointer inward. If the movement logic were reversed, the algorithm would miss the optimal solution. The implementation correctly follows the invariant that only the shorter boundary should move.

A final subtle case occurs when both heights are equal. Some implementations incorrectly move both pointers simultaneously, which can skip valid candidates. This solution moves only one pointer when heights are equal, preserving correctness while still guaranteeing linear complexity.