LeetCode 11 - Container With Most Water

This Medium array problem asks for the largest area formed by two vertical lines. Checking every pair is straightforward but takes O(n²) time, so I used two pointers starting at opposite ends of the array.

---

Problem link and explanation

• Problem: 11. Container With Most Water
• Summary: Choose two heights from an array and return the maximum amount of water the two lines and the x-axis can contain.

The distance between the indices determines the width. The shorter line determines the usable height, so a pair at left and right has an area of (right - left) * min(height[left], height[right]).

---

Approach

I placed left at the beginning and right at the end. After calculating the current area, I moved the pointer at the shorter line inward.

area = min(height[left], height[right]) * (right - left)
max_area = max(max_area, area)

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

Moving the taller line cannot improve the current limiting height, while the width becomes smaller. Moving the shorter line also reduces the width, but it creates a chance to find a taller boundary. That elimination rule removes the need to enumerate every possible pair.

---

Complexity analysis

• Time complexity: O(n)
  • One of the two pointers moves on every iteration, so the loop processes at most n - 1 pointer moves.
• Space complexity: O(1)
  • The solution uses two indices and a variable for the maximum area.

---

Implementation code

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:
            area = min(height[left], height[right]) * (right - left)
            max_area = max(max_area, area)

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

        return max_area

---

Summary and reflection

The useful part of this two-pointer solution is not just starting from both ends. The pointer movement follows the value that currently caps the result. Keeping the shorter line while reducing the width cannot produce a better area, so that branch can be discarded immediately. Thinking in terms of the limiting value made the movement rule easier to justify than memorizing it.