Container With Most Water | Leetcode 11

Welcome to our multi-language deep dive on Container With Most Water (Leetcode 11). This is visually and conceptually one of the absolute best problems for understanding Two-Pointer array sweeping logic.

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! The vertical height of your container natively is exactly limited to the shorter of the two bounding walls you select.

Example: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] => Output: 49 (Indices 1 [val 8] and 8 [val 7] act as bounding walls. Width = 8 - 1 = 7. Minimum Height = 7. Area = 7 * 7 = 49).

Approach 1: Two-Pointer Optimization O(N)

We conceptually want to maximize our area mathematically. Area = Width * Minimum_Height

Our goal is to hunt for the biggest Width and the biggest combination of wall heights concurrently. The sheer widest possible bounding box theoretically relies literally on the extreme 0th index and extreme (N-1) index pointers! Because this guarantees absolute max width mathematically organically.

From that theoretical absolute peak width... how can we incrementally optimize the internal area bounds dynamically without brute-forcing every single wall combo O(N^2)?

1. Calculate the real maximum native area utilizing the extreme left and right baseline walls against their dynamically calculated Width. Update maxArea.
2. Which array wall natively was physically shorter? The left, right, or equal? The shorter wall restricts the internal height permanently inside that window. The only theoretical mathematical method dynamically increasing your aggregated Area size bounds, is migrating inward shifting directly away from the smaller wall limit!
3. Shrink the bounding width dynamically continuously squeezing against the smaller of the two relative internal markers.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_area = 0
        left = 0
        right = len(height) - 1
        
        while left < right:
            # 1. Native Area dynamically bounds
            current_width = right - left
            current_height = min(height[left], height[right])
            
            # 2. Record maximums internally
            max_area = max(max_area, current_width * current_height)
            
            # 3. Step forward abandoning the inferior dynamic height marker definitively
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
                
        return max_area

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (11)