Container With Most Water

Difficulty: Medium Source: NeetCode

Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container that holds the most water. Return the maximum amount of water a container can store.

Note: You may not slant the container.

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

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Area Calculation — water held = min(height[left], height[right]) * (right - left)
• Two Pointers — greedy reasoning about which pointer to move inward
• Greedy Thinking — why moving the taller side inward can never improve the result

1. Brute Force

Intuition

Try every pair of lines and compute how much water they can hold. The water volume between two lines at indices i and j is min(height[i], height[j]) * (j - i). Track the maximum across all pairs.

Algorithm

1. Initialize max_water = 0.
2. For each pair (i, j) with i < j:
   • Compute water = min(height[i], height[j]) * (j - i).
   • Update max_water = max(max_water, water).
3. Return max_water.

Solution

def maxArea(height):
    max_water = 0
    n = len(height)
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            max_water = max(max_water, water)
    return max_water


print(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
print(maxArea([1, 1]))                          # 1
print(maxArea([4, 3, 2, 1, 4]))                # 16

Complexity

• Time: O(n²)
• Space: O(1)

2. Two Pointers (Greedy)

Intuition

Start with the widest possible container: left at index 0 and right at the last index. The water is limited by the shorter of the two walls. If we move the taller wall inward, the width decreases but the limiting height stays the same (or gets worse) — we can only possibly improve by moving the shorter wall inward, hoping to find a taller one that compensates for the lost width. So always move the pointer pointing to the shorter line inward.

Algorithm

1. Initialize left = 0, right = n - 1, max_water = 0.
2. While left < right:
   • Compute water = min(height[left], height[right]) * (right - left).
   • Update max_water.
   • If height[left] <= height[right]: increment left.
   • Else: decrement right.
3. Return max_water.

Solution

def maxArea(height):
    left, right = 0, len(height) - 1
    max_water = 0

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

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

    return max_water


print(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
print(maxArea([1, 1]))                          # 1
print(maxArea([4, 3, 2, 1, 4]))                # 16

Complexity

• Time: O(n)
• Space: O(1)

Common Pitfalls

Moving the taller pointer inward. This is the classic mistake. When you move the taller side, the new width is smaller and the bottleneck height is still bounded by the shorter side — you can’t gain anything. Always move the shorter side.

Using height[left] < height[right] instead of <=. When both heights are equal, it doesn’t matter which pointer you move — either choice is fine. Using <= for the left pointer (or >= for the right) handles ties correctly.

Forgetting to compute water before moving. Compute and potentially update max_water first, then decide which pointer to move. Moving first and computing after skips the current configuration.