Domain 2MediumCORE

Container With Most Water

We are given an array height where each element represents a vertical line at index i. We need to find two lines that form a container with the x-axis such that it holds the maximum amount of water (area). The area is calculated as $min(text{leftline}, text{rightline}) times (text{distance between them})$.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Two Pointers

11. Container With Most Water

Model: qwen3.5:9b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 52.9%


Problem Breakdown

We are given an array height where each element represents a vertical line at index i. We need to find two lines that form a container with the x-axis such that it holds the maximum amount of water (area). The area is calculated as min⁡(left_line,right_line)×(distance between them)\min(\text{left\_line}, \text{right\_line}) \times (\text{distance between them}).

Inputs: An array height of non-negative integers. Output: A single integer representing the maximum volume/area. Constraints & Edge Cases:

  • Array length nn is at least 2 (so a container can always be formed).
  • Heights are up to 10410^4, so area fits within standard integer types (Python handles large ints automatically anyway).
  • Since we need the maximum possible volume, an O(n2)O(n^2) brute force checking every pair is infeasible for n=105n=10^5. We strictly need a linear time solution.

Intuition

If I were to solve this naively, I would iterate through all pairs (i,j)(i, j) and calculate the area. That’s O(n2)O(n^2). With NN up to 10510^5, that’s roughly 10 billion operations—way too slow for a typical interview time limit (usually ~1 second).

To optimize this, I need to discard pairs without checking them if they can’t possibly beat the current maximum. The area is limited by the shorter of the two lines and their distance apart (width×min⁡(height)\text{width} \times \min(\text{height})). If we start with the widest possible container (leftmost index 0, rightmost index n−1n-1), any move inward reduces width. To potentially increase area after reducing width, we must find a taller line to compensate for that loss in distance. Crucially, moving the pointer pointing at the taller line will never help us get more water because the height is still capped by the shorter line on the other side; it just reduces our width unnecessarily. Therefore, I should always move the pointer associated with the shorter line inward to try and find a taller one that might increase the area.

Approach

I’ll use the Two Pointers technique:

  1. Initialize left at index 0 and right at index n−1n-1.
  2. Maintain a variable for max_area.
  3. While left < right:
    • Calculate current area using min⁡(height[left],height[right])\min(\text{height[left]}, \text{height[right]}) multiplied by (right - left).
    • Update max_area if the current is larger.
    • Move pointers: If height[left] < height[right], increment left. Otherwise, decrement right. (If heights are equal, moving either works; I’ll move one to be consistent).
  4. Return max_area.

Complexity Analysis

  • Time: O(n)O(n). The two pointers start at opposite ends and converge towards the center. In each iteration, we increment or decrement a pointer by exactly one step until they meet. We visit every element constant times.
  • Space: O(1)O(1). We only use variables for indices (left, right) and counters (max_area). No extra data structures are allocated based on input size.

Solution

def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        # Calculate current height (limited by the shorter line) and width
        h_min = min(height[left], height[right])
        w = right - left
        
        # Update maximum area found so far
        if h_min * w > max_area:
            max_area = h_min * w
            
        # Move the pointer of the shorter wall inward. 
        # Moving the taller one cannot increase the potential height, only decrease width.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
            
    return max_area

Edge Cases Handled

  • Minimum Length (n=2n=2): The loop runs once for indices 0 and 1, correctly calculating the single possible container.
  • All Heights Equal: min is always equal; pointers move inward one by one until they meet. Correctly calculates width ×\times height at each step (max will be found early or late depending on logic).
  • Zeros in Array: If a line has 0 height, the area becomes 0 immediately for that pair. The pointer moves past it to find non-zero heights if possible.
  • Large Heights/Widths: Python handles arbitrary precision integers, so overflow is not an issue even with 104×10510^4 \times 10^5.