python
# Pseudo-code for Brute Force
max_area = 0
for i from 0 to n-1:
    for j from i+1 to n-1:
        current_area = min(height[i], height[j]) * (j - i)
        max_area = max(max_area, current_area)
return max_area

Time Complexity: $O(n^2)$. We check $\frac{n(n-1)}{2}$ pairs. Why it fails: The constraints state that $n$ can be up to $10^5$. An $O(n^2)$ solution results in approximately $10^{10}$ operations, which far exceeds the standard time limit (usually around $10^8$ operations per second). This leads to a Time Limit Exceeded (TLE) error on large test cases.

Core Insight for Container With Most Water

The key intuition relies on the formula for the area: $\text{Area} = \min(\text{height}[left], \text{height}[right]) \times (right - left)$

To maximize the area, we want both the width and the height to be as large as possible. We start with the maximum possible width by placing pointers at the first and last indices.

From this state, we must decide which pointer to move inward. The decision is driven by the "bottleneck" of the container. The water level is constrained by the shorter line.

1. If we keep the shorter line and move the taller line inward, the width decreases. The new height cannot exceed the existing shorter line (the bottleneck). Therefore, the area is guaranteed to decrease or stay the same.
2. If we move the shorter line inward, the width decreases, but there is a possibility that we find a much taller line that compensates for the loss in width, resulting in a larger area.

Invariant: At every step, we can safely discard the shorter line because it cannot possibly form a larger area with any other line strictly inside the current window than it does with the current outer boundary.

Visual Description: Imagine the algorithm as a shrinking window. Initially, the window covers the entire array. We compare the values at the edges. If the left edge is lower than the right edge, we visually "cross out" the left index—it has reached its maximum potential area with the furthest possible pair (the right edge). We then shift the left boundary to the right. Conversely, if the right edge is lower, we cross it out and shift the right boundary to the left. We repeat this until the window closes.

Execution Flow

Let's trace the algorithm with the input height = [1, 8, 6, 2, 5, 4, 8, 3, 7].

1. Start: left = 0 (val 1), right = 8 (val 7).

   • Width = 8. Height = min(1, 7) = 1. Area = 8.
   • height[left] < height[right]. Move left to 1.

2. Step 2: left = 1 (val 8), right = 8 (val 7).

   • Width = 7. Height = min(8, 7) = 7. Area = 49. (Max updated).
   • height[right] < height[left]. Move right to 7.

3. Step 3: left = 1 (val 8), right = 7 (val 3).

   • Width = 6. Height = min(8, 3) = 3. Area = 18.
   • height[right] < height[left]. Move right to 6.

4. Step 4: left = 1 (val 8), right = 6 (val 8).

   • Width = 5. Height = min(8, 8) = 8. Area = 40.
   • Heights equal (arbitrarily move right). Move right to 5.

5. Step 5: left = 1 (val 8), right = 5 (val 4).

   • Width = 4. Height = min(8, 4) = 4. Area = 16.
   • height[right] < height[left]. Move right to 4.

6. Step 6: left = 1 (val 8), right = 4 (val 5).

   • Width = 3. Height = min(8, 5) = 5. Area = 15.
   • height[right] < height[left]. Move right to 3.

7. Step 7: left = 1 (val 8), right = 3 (val 2).

   • Width = 2. Height = min(8, 2) = 2. Area = 4.
   • height[right] < height[left]. Move right to 2.

8. Step 8: left = 1 (val 8), right = 2 (val 6).

   • Width = 1. Height = min(8, 6) = 6. Area = 6.
   • height[right] < height[left]. Move right to 1.

9. End: left meets right. Return Max Area: 49.

Proof of Correctness

To prove this greedy strategy works, consider the state where we have pointers at left and right, and assume height[left] < height[right].

The algorithm decides to move left to left + 1. This effectively discards all pairs (left, k) where left < k < right. Is it possible that one of these discarded pairs has a larger area than the current (left, right)?

• The width of any pair (left, k) is k - left. Since k < right, the width k - left is strictly less than right - left.
• The height of the pair (left, k) is min(height[left], height[k]). This value can be at most height[left].
• Therefore, the area of (left, k) is at most height[left] * (k - left), which is strictly less than height[left] * (right - left).

Thus, the pair (left, right) provides the maximum possible area involving the index left. We can safely discard left and narrow our search space without missing the global maximum.

Reference Implementation

C++ Solution for LeetCode 11

cpp
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int max_area = 0;

        while (left < right) {
            // Calculate current area
            int width = right - left;
            int current_height = min(height[left], height[right]);
            max_area = max(max_area, width * current_height);

            // Move the pointer corresponding to the shorter line
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max_area;
    }
};

Java Solution for LeetCode 11

java
class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            // Calculate current area
            int width = right - left;
            int currentHeight = Math.min(height[left], height[right]);
            maxArea = Math.max(maxArea, width * currentHeight);

            // Move the pointer corresponding to the shorter line
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

Python Solution for LeetCode 11

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

        while left < right:
            # Calculate current area
            width = right - left
            current_height = min(height[left], height[right])
            max_area = max(max_area, width * current_height)

            # Move the pointer corresponding to the shorter line
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        
        return max_area

Common Mistakes:

1. Moving the taller line instead of the shorter one:

   • Mistake: Some candidates attempt to keep the shorter line hoping that a closer line will be even taller.
   • Why: This reveals a misunderstanding of the area formula.
   • Consequence: Moving the taller line decreases width without increasing the effective height (which is capped by the shorter line). This logic fails to eliminate suboptimal states correctly and may miss the true maximum.

2. Moving both pointers inward simultaneously:

   • Mistake: Incrementing left and decrementing right in the same iteration regardless of heights.
   • Why: This is often an attempt to speed up the algorithm or a logic error assuming symmetry.
   • Consequence: This skips valid pairs. For example, if height[left] is very small and height[right] is huge, moving right inward might discard the optimal partner for a future left value.

3. Calculating area incorrectly:

   • Mistake: Using max(height[left], height[right]) instead of min.
   • Why: Confusing the physical constraint of water spilling over the shorter edge.
   • Consequence: The code returns incorrect, inflated values for the area.