Container with most Water

XXX. Container With Most Water

Array

Two Pointer

Problem Statement:

Given n non-negative integers representing heights of vertical lines, find two lines that together with x-axis forms a container that contains the most water.

• Container area = width × minimum height
• Width is distance between lines
• Find maximum possible area

Implementation:

public int maxArea(int[] height) {
    int left = 0;                          // Left pointer
    int right = height.length - 1;         // Right pointer
    int max = 0;                           // Maximum area found
    
    while (left < right) {
        // Calculate current area
        int area = (right - left) * Math.min(height[left], height[right]);
        
        // Update maximum area if necessary
        if (area > max) 
            max = area;
        
        // Move pointer with smaller height inward
        if (height[left] > height[right]) 
            right--;
        else 
            left++;
    }
    
    return max;
}

Complexity:

Time Complexity: O(n), single pass through array
Space Complexity: O(1), constant extra space

Key Points:

• **Area Calculation**:
  • Area = width × min(height1, height2)
  • Width = right - left
  • Update max area if current is larger
• **Pointer Movement**:
  • Always move pointer with smaller height
  • Moving larger height can only decrease area
  • Continue until pointers meet
• **Optimization**:
  • No need to check every possible combination
  • Greedy approach moving inward
  • Moving smaller height may find larger area

Example:

For array [1,8,6,2,5,4,8,3,7]:

• Start with widest container (index 0 and 8)
• Move pointers inward keeping track of max area
• Final answer: 49 (using height 7 and 7 with width 7)

Why It Works:

• **Moving Pointers**:
  • Moving larger height can only reduce area
  • Moving smaller height might increase area
  • Never need to move back outward
• **Proof of Correctness**:
  • Can't miss maximum area
  • All potentially larger areas are checked
  • Greedy choice is optimal at each step