[AlgoMastery]
Topics›Array›Container With Most Water
📖

Container With Most Water

Array
~20 min read
5 practice problems

Overview

Container With Most Water problem finds two lines that together with x-axis form a container holding the most water. Unlike trapping rain water, this problem focuses on maximizing the area between two lines.

The key insight: area = width × min(height[left], height[right]). Use two pointers, always move the pointer with smaller height, as moving the taller one can only decrease area.

Container with water is particularly useful for:

  • Understanding two-pointer technique
  • Greedy algorithm thinking
  • Area optimization problems
  • Real-world container problems

Pattern 1: Two Pointers (Optimal)

Most efficient O(n) solution.

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;
  
  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(height[left], height[right]);
    const area = width * minHeight;
    maxWater = Math.max(maxWater, area);
    
    // Move pointer with smaller height
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  
  return maxWater;
}

Time: O(n), Space: O(1)

Key insight: Always move pointer with smaller height. Moving taller pointer can only decrease area.

Pattern 2: Brute Force

Check all pairs of lines.

function maxAreaBruteForce(height: number[]): number {
  let maxWater = 0;
  
  for (let i = 0; i < height.length; i++) {
    for (let j = i + 1; j < height.length; j++) {
      const width = j - i;
      const minHeight = Math.min(height[i], height[j]);
      const area = width * minHeight;
      maxWater = Math.max(maxWater, area);
    }
  }
  
  return maxWater;
}

Time: O(n²), Space: O(1)

Not recommended for large inputs.

Pattern 3: Two Pointers with Early Termination

Optimized with early termination.

function maxAreaOptimized(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;
  
  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(height[left], height[right]);
    maxWater = Math.max(maxWater, width * minHeight);
    
    // Move pointer with smaller height
    // Skip all heights smaller than current min
    if (height[left] < height[right]) {
      const currentLeft = height[left];
      while (left < right && height[left] <= currentLeft) {
        left++;
      }
    } else {
      const currentRight = height[right];
      while (left < right && height[right] <= currentRight) {
        right--;
      }
    }
  }
  
  return maxWater;
}

Time: O(n), Space: O(1)

Optimization: Skip heights that can't improve area.

Pattern 4: Container With Most Water (Return Indices)

Return indices of the two lines.

function maxAreaWithIndices(height: number[]): [number, number, number] {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;
  let bestLeft = 0;
  let bestRight = 0;
  
  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(height[left], height[right]);
    const area = width * minHeight;
    
    if (area > maxWater) {
      maxWater = area;
      bestLeft = left;
      bestRight = right;
    }
    
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  
  return [maxWater, bestLeft, bestRight];
}

Time: O(n), Space: O(1)

Pattern 5: Container With K Most Water

Find K containers with most water.

function kMaxContainers(height: number[], k: number): Array<[number, number, number]> {
  const containers: Array<[number, number, number]> = [];
  
  // Generate all valid containers
  for (let i = 0; i < height.length; i++) {
    for (let j = i + 1; j < height.length; j++) {
      const width = j - i;
      const minHeight = Math.min(height[i], height[j]);
      const area = width * minHeight;
      containers.push([area, i, j]);
    }
  }
  
  // Sort by area descending
  containers.sort((a, b) => b[0] - a[0]);
  
  return containers.slice(0, k);
}

Time: O(n² log n), Space: O(n²)

Pattern 6: Container With Most Water (3D)

Find container with most water in 3D grid.

function maxArea3D(grid: number[][]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  let maxArea = 0;
  
  // Try all pairs of rows
  for (let i = 0; i < rows; i++) {
    for (let j = i + 1; j < rows; j++) {
      // For each column, find min height between rows
      let area = 0;
      for (let k = 0; k < cols; k++) {
        const minHeight = Math.min(grid[i][k], grid[j][k]);
        area += minHeight;
      }
      maxArea = Math.max(maxArea, area * (j - i));
    }
  }
  
  return maxArea;
}

Time: O(rows² * cols), Space: O(1)

Pattern 7: Container With Most Water (With Obstacles)

Find container accounting for obstacles.

function maxAreaWithObstacles(height: number[], obstacles: Set<number>): number {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;
  
  // Skip obstacles at boundaries
  while (left < right && obstacles.has(left)) left++;
  while (left < right && obstacles.has(right)) right--;
  
  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(height[left], height[right]);
    maxWater = Math.max(maxWater, width * minHeight);
    
    if (height[left] < height[right]) {
      left++;
      while (left < right && obstacles.has(left)) left++;
    } else {
      right--;
      while (left < right && obstacles.has(right)) right--;
    }
  }
  
  return maxWater;
}

Time: O(n), Space: O(n)

Pattern 8: Container With Most Water (Circular)

Find container in circular array.

function maxAreaCircular(height: number[]): number {
  const n = height.length;
  let maxWater = 0;
  
  // Try all starting positions
  for (let start = 0; start < n; start++) {
    let left = start;
    let right = (start + 1) % n;
    
    while (right !== start) {
      const width = (right - left + n) % n;
      const minHeight = Math.min(height[left], height[right]);
      maxWater = Math.max(maxWater, width * minHeight);
      
      if (height[left] < height[right]) {
        left = (left + 1) % n;
        if (left === start) break;
      } else {
        right = (right - 1 + n) % n;
        if (right === start) break;
      }
    }
  }
  
  return maxWater;
}

Time: O(n²), Space: O(1)

Pattern 9: Container With Most Water (Multiple Containers)

Find maximum total water from multiple non-overlapping containers.

function maxMultipleContainers(height: number[], k: number): number {
  const n = height.length;
  
  // DP: dp[i][j] = max water using first i lines with j containers
  const dp = Array(n + 1).fill(null).map(() => Array(k + 1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= k; j++) {
      dp[i][j] = dp[i - 1][j];
      
      // Try all possible left boundaries
      for (let left = 0; left < i; left++) {
        const width = i - left - 1;
        const minHeight = Math.min(height[left], height[i - 1]);
        const area = width * minHeight;
        dp[i][j] = Math.max(dp[i][j], dp[left][j - 1] + area);
      }
    }
  }
  
  return dp[n][k];
}

Time: O(n² k), Space: O(n k)

Pattern 10: Container With Most Water (Greedy Variants)

Different greedy strategies.

// Strategy 1: Always move towards taller line
function maxAreaGreedy1(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;
  
  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(height[left], height[right]);
    maxWater = Math.max(maxWater, width * minHeight);
    
    // Move towards potentially taller line
    if (height[left + 1] > height[right - 1]) {
      left++;
    } else {
      right--;
    }
  }
  
  return maxWater;
}

// Strategy 2: Move pointer with smaller next height
function maxAreaGreedy2(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;
  
  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(height[left], height[right]);
    maxWater = Math.max(maxWater, width * minHeight);
    
    // Move pointer with smaller next height
    const nextLeft = left + 1 < height.length ? height[left + 1] : 0;
    const nextRight = right - 1 >= 0 ? height[right - 1] : 0;
    
    if (nextLeft > nextRight) {
      left++;
    } else {
      right--;
    }
  }
  
  return maxWater;
}

Note: These variants may not always find optimal solution.

When to Use Container With Water Techniques

Use container with water techniques when:

  • Problem asks for maximum area between two lines
  • Need to optimize area calculation
  • Two-pointer technique applicable
  • Greedy algorithm thinking needed
  • Similar to trapping rain water but different goal

Key distinction: Container with water maximizes area between two lines, while trapping rain water calculates total trapped water.

Template (Two Pointers)

function maxAreaTemplate(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;
  
  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(height[left], height[right]);
    maxWater = Math.max(maxWater, width * minHeight);
    
    // Always move pointer with smaller height
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  
  return maxWater;
}

Time and Space Complexity Summary

  • Two pointers: O(n) time, O(1) space
  • Brute force: O(n²) time, O(1) space
  • Optimized two pointers: O(n) time, O(1) space
  • K containers: O(n² log n) time, O(n²) space
  • 3D version: O(rows² * cols) time, O(1) space
  • Circular: O(n²) time, O(1) space

Practice Tips

  1. Understand formula - Area = width × min(height[left], height[right])
  2. Greedy choice - Always move pointer with smaller height
  3. Why it works - Moving taller pointer can only decrease area
  4. Visualization - Draw lines to understand area calculation
  5. Edge cases - Empty array, two elements, all same height

Common Mistakes

  1. Wrong formula - Not using min of two heights
  2. Wrong pointer movement - Moving taller pointer instead of shorter
  3. Index errors - Off-by-one in width calculation
  4. Not updating max - Forgetting to update maxWater in each iteration
  5. Edge cases - Not handling arrays with < 2 elements

Related Concepts

  • Two Pointers - Core technique
  • Greedy Algorithm - Always move smaller pointer
  • Trapping Rain Water - Similar but different problem
  • Area Calculation - Mathematical foundation

Container with most water is a classic two-pointer problem. Master the greedy approach of always moving the pointer with smaller height for optimal O(n) solution in coding interviews.

← PreviousTrapping Rain WaterNext →Array Transformation