Container with Most Water Problem

Problem Description

You are given an array height where each element represents the height of a vertical line drawn at that position on the x-axis.

• Goal: Find two lines that form a container with the maximum area of water.
• The formula for the area of a container is: Area=Width×Height where:
  • Width: The distance between the two lines’ x-coordinates.
  • Height: The shorter of the two lines.

For example, if height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

• The two lines at index 1 and 8 form the maximum container.
• Width = 8−1= 7
• Height = min⁡(8,7)=7
• Max Area = 7×7=49

Solution Approaches

1️⃣ Brute Force

• Idea: Check the area for all possible pairs of lines.
• Steps:
  1. Iterate through all pairs of lines using nested loops.
  2. Calculate the area for each pair.
  3. Track the maximum area found.
• Code:

  def max_area_brute_force(height):
      n = len(height)
      max_area = 0
  
      for i in range(n):
          for j in range(i + 1, n):
              width = j - i
              current_height = min(height[i], height[j])
              current_area = width * current_height
              max_area = max(max_area, current_area)
  
      return max_area
  
  # Example Input
  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
  result = max_area_brute_force(height)
  print("Max Area (Brute Force):", result)
  

• Time Complexity: O(n^2)
  We compare every pair of lines, which takes quadratic time.
• Space Complexity: O(1)
  No additional space is required.

2️⃣ Optimized Approach (Two Pointers)

• Idea: Use two pointers to efficiently find the maximum area. Start with the widest container (outermost lines) and adjust inward.
• Steps:
  1. Place two pointers, left at the beginning and right at the end of the array.
  2. Calculate the area between the two lines.
  3. Update the maximum area if the new area is larger.
  4. Move the pointer pointing to the shorter line inward, as the height is the limiting factor for the area.
  5. Repeat until the two pointers meet.
• Code:

  def max_area(height):
      left = 0
      right = len(height) - 1
      max_area = 0
  
      while left < right:
          width = right - left
          current_height = min(height[left], height[right])
          current_area = width * current_height
          max_area = max(max_area, current_area)
  
          # Move the shorter line
          if height[left] <= height[right]:
              left += 1
          else:
              right -= 1
  
      return max_area
  
  # Example Input
  height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
  result = max_area(height)
  print("Max Area (Two Pointers):", result)
  

• Time Complexity: O(n)
  Each element is processed at most once.
• Space Complexity: O(1)
  No extra space is used.

Comparison of Approaches

The two-pointer approach is the most efficient solution and works well for large input arrays.