Container With Most Water

Container With Most Water

January 8, 2024
medium
Two Pointers

Problem #

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis, forms a container, such that the container contains the most water. You may not slant the container.

Example:

  1. Input: [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The max area of water the container can contain is 49.

Solution #

The solution uses a two-pointer approach. Start with one pointer at the beginning and one at the end of the array. Calculate the area between the two pointers and update the maximum area found so far. Then, move the pointer pointing to the shorter line towards the other pointer. This is because moving the longer line will not increase the area. The process is repeated until the two pointers meet.

Algorithm Steps #

  1. Initialize two pointers, left at the start and right at the end of the array.
  2. Initialize a variable maxArea to store the maximum area found.
  3. While left is less than right:
    • Calculate the area with min(height[left], height[right]) * (right - left) and update maxArea.
    • Move the pointer with the shorter height inwards.
  4. Return maxArea.

Code (Python) # 

def maxArea(height):
    left, right = 0, len(height) - 1
    maxArea = 0

    while left < right:
        width = right - left
        currentArea = min(height[left], height[right]) * width
        maxArea = max(maxArea, currentArea)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return maxArea

# Test the function
print(maxArea([1,8,6,2,5,4,8,3,7]))  # Output: 49

Time Complexity #

The time complexity is O(n), where n is the number of elements in the array. This is due to the single pass through the array.

Space Complexity #

The space complexity is O(1), as no extra space is needed apart from variables for iteration and calculation.