Container With Most Water

Problem Statement

Given an array of heights, find two lines that together with x-axis form a container holding the most water.

Example: heights = [1,8,6,2,5,4,8,3,7] → Output: 49

Problem Statement

Given an array of heights, find two lines that together with x-axis form a container holding the most water.

Example: heights = [1,8,6,2,5,4,8,3,7] → Output: 49

Approach 1: Brute Force

Explanation: Check every pair of lines and calculate area.

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

        max_area = 0
        for i = 0 to n-1:
        for j = i+1 to n-1:
        area = min(height[i], height[j]) * (j - i)
        max_area = max(max_area, area)
        return max_area

Approach 1: Brute Force

Explanation: Check every pair of lines and calculate area.

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

        max_area = 0
        for i = 0 to n-1:
        for j = i+1 to n-1:
        area = min(height[i], height[j]) * (j - i)
        max_area = max(max_area, area)
        return max_area

Approach 2: Two Pointers (Optimal)

Explanation: Use two pointers at ends, move the smaller height pointer.

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

    
      Approach 2: Two Pointers (Optimal)
      
        Explanation: Use two pointers at ends, move the
        smaller height pointer.
      
      Time: O(n), Space: O(1)
      left = 0, right = n-1
max_area = 0
while left < right:
  area = min(height[left], height[right]) * (right - left)
  max_area = max(max_area, area)
  if height[left] < height[right]: left++
  else: right--
return max_area
      
      

    

    
      Approach 3: Explanation + Visualization
      
        Explanation: Moving the smaller line may increase
        height without decreasing width too much, ensuring we cover maximum
        area. This guarantees we find optimal solution in one pass.
      
      Time: O(n), Space: O(1)
          
      Approach 3: Explanation + Visualization
      
        Explanation: Moving the smaller line may increase
        height without decreasing width too much, ensuring we cover maximum
        area. This guarantees we find optimal solution in one pass.
      
      Time: O(n), Space: O(1)
      same as two-pointer method