Problem Statement

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.

Example

Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines form a container with 9 units of water.

Solution

The problem requires finding the container with maximum water, where the height of the container is the height of the shorter line between two lines and the width of the container is the distance between the two lines.

One approach to solve this problem is by using the two pointers technique. Let's call the two pointers left and right, initialized to the start and end of the input array respectively.

We start with the widest possible container, which is formed using the first and last line. Then, we update the pointers as follows:

• If height[left] < height[right], it means the container's height is limited by the left line, so we move the left pointer one step forward, considering the possibility of finding a higher line.
• If height[left] >= height[right], it means the container's height is limited by the right line, so we move the right pointer one step backward, considering the possibility of finding a higher line.

We keep track of the maximum area encountered so far and continue updating it until the pointers meet (i.e., left >= right).

Pseudocode

function maxArea(height):
    left = 0
    right = length(height) - 1
    maxArea = 0
    
    while left < right:
        containerHeight = min(height[left], height[right])
        containerWidth = right - left
        area = containerHeight * containerWidth
        maxArea = max(maxArea, area)
        
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return maxArea

The time complexity of this solution is O(n), where n is the length of the input array. This is because we are iterating through the array once using the two pointers technique.