LeetCode 11: Container With Most Water

Problem Statement

Given an array of non-negative integers representing heights of vertical lines on a coordinate plane, find two lines that, together with the x-axis, form a container holding the most water. The array length is at least 2, and each element represents the height at that index.

Constraints

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

Example

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: Lines at indices 1 (height 8) and 8 (height 7) trap 49 units of water (width 7 * min(8, 7)).

Input: height = [1,1]
Output: 1
Explanation: Lines at indices 0 and 1 (both height 1) trap 1 unit (width 1 * min(1, 1)).

Input: height = [4,3,2,1,4]
Output: 16
Explanation: Lines at indices 0 (height 4) and 4 (height 4) trap 16 units (width 4 * min(4, 4)).

Understanding the Problem

Imagine vertical lines on a graph where each number in the array is the height of a line at its position. We need to pick two lines that, with the x-axis, form a container holding the most water. Water volume is the width (distance between indices) times the height (minimum of the two lines). We’ll use a two-pointer approach to solve this efficiently.

Solution: Two-Pointer Approach

Explanation

Start with pointers at both ends of the array and move them inward, calculating water at each step and keeping the maximum. Move the pointer at the shorter line to try for a taller one, maximizing the area.

Initialize pointers at the start (left) and end (right) of the array, and set max water to 0.
Calculate water at the current pointers: width (right - left) times the shorter height.
Update max water if the current amount is greater.
Move the pointer at the shorter height inward (left if left height is smaller, right if right height is smaller).
Repeat until pointers meet, then return max water.

Step-by-Step Example

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

We have heights [1,8,6,2,5,4,8,3,7] and want the most water.

Goal: Find two lines trapping the most water.
Result for reference: Indices 1 and 8 (heights 8 and 7) give 49 units.
Start: Left pointer at 0, right at 8, max water at 0.
Step 1: Left at 0 (height 1), right at 8 (height 7).

Width = 8 - 0 = 8.
Height = min(1, 7) = 1.
Water = 8 * 1 = 8.
Max water = 8.
Move left (1 < 7), left to 1.

Step 2: Left at 1 (height 8), right at 8 (height 7).

Width = 8 - 1 = 7.
Height = min(8, 7) = 7.
Water = 7 * 7 = 49.
Max water = 49.
Move right (7 < 8), right to 7.

Step 3: Left at 1 (height 8), right at 7 (height 3).

Width = 7 - 1 = 6.
Height = min(8, 3) = 3.
Water = 6 * 3 = 18.
Max water stays 49.
Move right (3 < 8), right to 6.

Step 4: Left at 1 (height 8), right at 6 (height 8).

Width = 6 - 1 = 5.
Height = min(8, 8) = 8.
Water = 5 * 8 = 40.
Max water stays 49.
Heights equal, move either (say right), right to 5.

Step 5: Left at 1 (height 8), right at 5 (height 4).

Width = 5 - 1 = 4.
Height = min(8, 4) = 4.
Water = 4 * 4 = 16.
Max water stays 49.
Move right (4 < 8), right to 4.

Step 6: Left at 1 (height 8), right at 4 (height 5).

Width = 4 - 1 = 3.
Height = min(8, 5) = 5.
Water = 3 * 5 = 15.
Max water stays 49.
Move right (5 < 8), right to 3.

Step 7: Left at 1 (height 8), right at 3 (height 2).

Width = 3 - 1 = 2.
Height = min(8, 2) = 2.
Water = 2 * 2 = 4.
Max water stays 49.
Move right (2 < 8), right to 2.

Step 8: Left at 1 (height 8), right at 2 (height 6).

Width = 2 - 1 = 1.
Height = min(8, 6) = 6.
Water = 1 * 6 = 6.
Max water stays 49.
Move right (6 < 8), right to 1.

Step 9: Left meets right, stop.
Finish: Return 49.

The max water found is 49, from indices 1 and 8.

Example 2: height = [1,1]

Now, heights are [1,1].

Goal: Find the most water with two lines.
Result for reference: Width 1, height 1, water 1.
Start: Left at 0, right at 1, max water at 0.
Step 1: Left at 0 (height 1), right at 1 (height 1).

Width = 1 - 0 = 1.
Height = min(1, 1) = 1.
Water = 1 * 1 = 1.
Max water = 1.
Heights equal, move either (say right), right to 0.

Step 2: Left meets right, stop.
Finish: Return 1.

Only one pair, water is 1.

Code

Here’s the Python code to solve LeetCode 11. It’s efficient and works in Python 3.6+. Test it on Replit!

def maxArea(height: list[int]) -> int:
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        min_height = min(height[left], height[right])
        current_water = width * min_height
        max_water = max(max_water, current_water)

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

    return max_water

Note: Curious about Python’s min() function? Check the official docs.

Complexity

Time Complexity: O(n) – One pass with two pointers.
Space Complexity: O(1) – Just a few variables.

Efficiency Notes

This two-pointer method is optimal for LeetCode 11, cutting time from O(n²) (checking all pairs) to O(n) by smartly shrinking the search space.

Key Insights

Tips to master LeetCode 11:

Start Wide: Begin at the ends for maximum width—it’s your best shot at big water.
Move the Short Side: Shifting the shorter line might find a taller one, increasing height potential.
Skip Brute Force: Checking every pair wastes time—two pointers are the trick.

These insights make the problem click!

Alternative: Brute Force (Brief Mention)

You could check every pair of lines, calculating water for each (O(n²)), but it’s slow for large arrays. The two-pointer approach is far better.

Additional Example

For height = [4,3,2,1,4]:

Goal: Max water.
Reference: Indices 0 and 4 (both 4), width 4, water 16.
Steps: Left 0, right 4, water 16; others smaller.
Result: 16.

Edge Cases

Two Lines: [1,1] – Returns 1.
All Same: [2,2,2] – Returns 4.
One Tall: [1,100,1] – Returns 2.

Final Thoughts

The two-pointer solution is a slick way to solve LeetCode 11: Container With Most Water in Python. It’s efficient and great for interviews. Want more array challenges? Try LeetCode 1: Two Sum.