leetcode-11 Container With Most Water

[11] Container With Most Water

Key Concept: Two Pointers with Greedy Strategy - Start with the widest container and move the pointer pointing to the shorter line inward, as the height is limited by the shorter line.

Why move the shorter pointer? Moving the taller pointer can only decrease the area (width decreases, height stays same or decreases). Moving the shorter pointer might find a taller line and increase area.

# You are given an integer array height of length n. There are n vertical lines
# 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 that contains
# the most water. Return the maximum amount of water a container can store.
#
# Example 1:
# Input: height = [1,8,6,2,5,4,8,3,7]
# Output: 49
# Explanation: The vertical lines are represented by [1,8,6,2,5,4,8,3,7].
# The max area is between index 1 and 8, area = min(8,7) * (8-1) = 49
#
# Example 2:
# Input: height = [1,1]
# Output: 1
#
# Constraints:
# n == height.length
# 2 <= n <= 10^5
# 0 <= height[i] <= 10^4

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

            # Move the pointer pointing to shorter line
            # This is greedy: moving the taller pointer can only decrease area
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

# Time Complexity: O(n) - single pass with two pointers
# Space Complexity: O(1) - only using constant extra space