🟨 Container With Most Water (#11)

🔗 Problem Link

• LeetCode - Container With Most Water
• NeetCode - Container With Most Water

📋 Problem Statement

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

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Note: You may not slant the container.

💡 Examples

Example 1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The vertical lines are at positions (1,1), (2,8), (3,6)...
The max area is between lines at index 1 and 8: min(8,7) * (8-1) = 49

Example 2

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

🔑 Key Insights & Approach

Core Observation: Start with widest container, move pointer of shorter line inward (only way to potentially increase area).

Why Two Pointers from Ends?

• Start with maximum width
• Moving shorter line is the only way to potentially get larger area
• O(n) time, single pass
• Greedy approach works because we explore best options

Approaches:

1. Brute force all pairs: O(n²)
2. Two pointers from ends: O(n) - optimal

Pattern: "Two Pointers - Opposite Ends" pattern for optimization problems.

🐍 Solution: Python

Approach: Two Pointers

Time Complexity: O(n) | Space Complexity: O(1)

from typing import List

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

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

            max_area = max(max_area, current_area)

            # Move pointer of shorter line
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

Approach 2: With Explanation

Time Complexity: O(n) | Space Complexity: O(1)

from typing import List

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

        while left < right:
            # Area = width * min(left_height, right_height)
            width = right - left
            min_height = min(height[left], height[right])
            max_water = max(max_water, width * min_height)

            # Move the pointer pointing to shorter line
            # This is greedy: only by increasing min_height can we get larger area
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1

        return max_water

🔵 Solution: Golang

Approach: Two Pointers

Time Complexity: O(n) | Space Complexity: O(1)

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0

    for left < right {
        // Calculate current area
        width := right - left
        minHeight := min(height[left], height[right])
        currentArea := width * minHeight

        if currentArea > maxArea {
            maxArea = currentArea
        }

        // Move pointer of shorter line
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }

    return maxArea
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

📚 References

• NeetCode - Container With Most Water