💬 Discord
Sign In
NeetCode #203LC-11MediumTwo PointersBlind 75NC 150NC 250
← Back to All Problems

#203 · #11 · Container With Most Water(盛最多水的容器)

📌 Problem Statement & Constraints

You are given an array height of n non-negative integers representing vertical lines. Find two lines that, together with the x-axis, form a container holding the most water. Return the maximum area. Constraints: 2 <= n <= 10^5, 0 <= height[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. The area for a pair (i, j) is min(height[i], height[j]) * (j - i).
  2. Start with the widest possible container: pointers at both ends. The width can only shrink, so any improvement must come from a taller minimum.
  3. Move the pointer pointing at the shorter line inward. Moving the taller one cannot help, since the width shrinks and the minimum is unchanged or worse.
  4. This greedy is provably optimal: the pointer that moves is the one whose current pairing can never beat the recorded best.

💻 Benchmark Python3 Implementation

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j = 0, len(height) - 1
        best = 0
        while i < j:
            h = min(height[i], height[j])
            best = max(best, h * (j - i))
            if height[i] < height[j]:
                i += 1                     # move the shorter side inward
            else:
                j -= 1
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each pointer moves at most n steps in total.
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Moving the taller pointer: that can never improve the area, because the width shrinks while the limiting height stays the same or decreases.
  • Trying every pair: O(n^2) = 10^10 for n = 10^5, far too slow.
  • Using height[i] <= height[j] to decide: ties can go either way; both choices are equivalent, but the branch must still move exactly one pointer.
  • Forgetting that the minimum is what limits the area: multiplying by the taller line is a common mistake.