Problem Description

You have an integer array height of length n. Each element height[i] represents the height of a vertical line drawn at position i on the x-axis. Specifically, the i-th line has endpoints at coordinates (i, 0) and (i, height[i]).

Your task is to select any two lines from these n vertical lines that, together with the x-axis, form a container. The container will hold water, and the amount of water it can hold is determined by:

• The distance between the two selected lines (width of the container)
• The height of the shorter of the two selected lines (since water would overflow from the shorter side)

The area of water the container can hold is calculated as: min(height[left], height[right]) × (right - left), where left and right are the indices of the two selected lines.

You need to find the maximum amount of water that can be stored by choosing the optimal pair of lines. Note that the container cannot be tilted or slanted - it must remain upright.

For example, if height = [1,8,6,2,5,4,8,3,7], you might choose the lines at indices 1 and 8 (with heights 8 and 7). The container width would be 8 - 1 = 7, and the water height would be min(8, 7) = 7, giving a total area of 7 × 7 = 49.

Return the maximum area of water that can be contained.

Intuition

Let's start with the brute force approach: we could check every possible pair of lines and calculate the water area for each pair, keeping track of the maximum. This would require checking n × (n-1) / 2 pairs, giving us O(n²) time complexity. Can we do better?

The key insight is that we can use two pointers starting from the widest possible container - one at the leftmost line (l = 0) and one at the rightmost line (r = n-1). This gives us the maximum possible width to start with.

Now, why can we safely move pointers inward without missing the optimal solution? Consider what happens when we have two lines at positions l and r:

• The current area is min(height[l], height[r]) × (r - l)
• If we move either pointer inward, the width (r - l) will definitely decrease
• For the area to increase despite the reduced width, we need a taller line

Here's the crucial observation: we should always move the pointer pointing to the shorter line. Why?

If height[l] < height[r] and we move the right pointer left, any new container formed with the current left line will have:

• A smaller width than before
• A height that's still limited by height[l] (since it's the shorter one)

This means moving the pointer at the taller line can never give us a better result with the current shorter line. However, if we move the pointer at the shorter line, we might find a taller line that could potentially create a larger area despite the reduced width.

This greedy strategy ensures we explore all potentially optimal solutions while eliminating combinations that cannot possibly be better than what we've already found. By always moving the pointer at the shorter line, we're essentially saying: "This shorter line is the limiting factor, let's try to find a better one."

The algorithm continues until the two pointers meet, at which point we've considered all viable containers and can return the maximum area found.

Learn more about Greedy and Two Pointers patterns.

Solution Approach

We implement the two-pointer technique to solve this problem efficiently in O(n) time.

Initial Setup:

• Initialize two pointers: l = 0 (left pointer at the start) and r = len(height) - 1 (right pointer at the end)
• Initialize ans = 0 to track the maximum water area found

Main Algorithm:

We use a while loop that continues as long as l < r:

1. Calculate Current Area:

   • The current water area is min(height[l], height[r]) * (r - l)
   • Store this in a variable t
   • Update ans to be the maximum of the current ans and t

2. Move Pointers:

   • Compare the heights at the two pointers
   • If height[l] < height[r], increment l (move left pointer right)
   • Otherwise, decrement r (move right pointer left)
   • This ensures we always move the pointer pointing to the shorter line

Why This Works:

The algorithm systematically explores potentially optimal containers while pruning those that cannot be better:

• Starting with the widest container guarantees we don't miss any wide containers that might be optimal
• Moving the shorter line's pointer is optimal because keeping it while reducing width cannot improve the area
• Each iteration either finds a better solution or eliminates a line from consideration
• After n-1 iterations, all possible optimal containers have been considered

Time and Space Complexity:

• Time: O(n) - each element is visited at most once as pointers move toward each other
• Space: O(1) - only using a constant amount of extra space for pointers and variables

The final result ans contains the maximum water area that can be stored.

Example Walkthrough

Let's walk through a small example with height = [1, 3, 2, 4, 2].

Initial Setup:

• Left pointer l = 0 (height = 1)
• Right pointer r = 4 (height = 2)
• Maximum area ans = 0

Iteration 1:

• Current container: lines at indices 0 and 4
• Width = 4 - 0 = 4
• Height = min(1, 2) = 1 (limited by the shorter line)
• Area = 1 × 4 = 4
• Update: ans = 4
• Since height[0] = 1 < height[4] = 2, move left pointer: l = 1

Iteration 2:

• Current container: lines at indices 1 and 4
• Width = 4 - 1 = 3
• Height = min(3, 2) = 2
• Area = 2 × 3 = 6
• Update: ans = 6 (new maximum!)
• Since height[1] = 3 > height[4] = 2, move right pointer: r = 3

Iteration 3:

• Current container: lines at indices 1 and 3
• Width = 3 - 1 = 2
• Height = min(3, 4) = 3
• Area = 3 × 2 = 6
• Keep: ans = 6 (no improvement)
• Since height[1] = 3 < height[3] = 4, move left pointer: l = 2

Iteration 4:

• Current container: lines at indices 2 and 3
• Width = 3 - 2 = 1
• Height = min(2, 4) = 2
• Area = 2 × 1 = 2
• Keep: ans = 6 (no improvement)
• Since height[2] = 2 < height[3] = 4, move left pointer: l = 3

Termination:

• Now l = 3 and r = 3, so l < r is false
• Algorithm terminates
• Return ans = 6

The maximum water area is 6, formed by the lines at indices 1 and 4, with a width of 3 and height of 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array height. The algorithm uses a two-pointer approach that starts from both ends of the array. In each iteration of the while loop, either the left pointer l moves right or the right pointer r moves left, but never both. Since the pointers start at opposite ends and move toward each other, they will meet after at most n-1 iterations. Each iteration performs constant time operations (calculating area, comparing values, updating pointers), resulting in a linear time complexity.

Space Complexity: O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. The variables l, r, ans, and t are the only additional storage used, and their space requirement doesn't scale with the input size n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Moving Both Pointers Simultaneously

A common mistake is trying to "optimize" by moving both pointers when heights are equal, thinking it might speed up the algorithm:

Incorrect approach:

if height[left] < height[right]:
    left += 1
elif height[left] > height[right]:
    right -= 1
else:
    # Wrong: Moving both pointers when equal
    left += 1
    right -= 1

Why it's wrong: Moving both pointers simultaneously can cause you to skip potentially optimal containers. For example, if both current heights are equal but the next element from one side is much taller, you'd miss that combination.

Correct approach: Move only one pointer even when heights are equal:

if height[left] < height[right]:
    left += 1
else:
    right -= 1  # This handles both > and == cases

2. Incorrect Area Calculation

Another pitfall is calculating the area incorrectly by using indices instead of the distance between them:

Incorrect:

current_area = min(height[left], height[right]) * min(left, right)
# or
current_area = min(height[left], height[right]) * max(left, right)

Correct:

current_area = min(height[left], height[right]) * (right - left)

3. Off-by-One Errors with Initial Pointer Positions

Some might incorrectly initialize pointers:

Incorrect:

left = 0
right = len(height)  # Wrong: index out of bounds

Correct:

left = 0
right = len(height) - 1  # Correct: last valid index

4. Forgetting Edge Cases

Not handling arrays with fewer than 2 elements (though most problems guarantee n ≥ 2):

Robust solution:

def maxArea(self, height: List[int]) -> int:
    if len(height) < 2:
        return 0
  
    left = 0
    right = len(height) - 1
    max_area = 0
    # ... rest of the code