This problem evaluates the your ability to work with arrays and implement a problem involving multiple indices.

Solution 1: Brute Force

There is a solution that involves a brute-force approach where we check the area for all possible pairs of lines.

Below is a Python implementation of the max_area function to find the maximum area of water that can be contained by two lines:

from typing import List

def max_area_bruteforce(height: List[int]) -> int:
    """
    Return the maximum area of water that can be contained by two lines (brute-force approach).

    Parameters:
    - height: List of non-negative integers representing the height of each line.

    Returns:
    - int: Maximum area of water.
    """
    max_area = 0
    n = len(height)

    for i in range(n - 1):
        for j in range(i + 1, n):
            h = min(height[i], height[j])
            w = j - i
            max_area = max(max_area, h * w)

    return max_area

# Example usage:
height1 = [1, 8, 6, 2, 5, 4, 8, 3, 7]
result1 = max_area_bruteforce(height1)
print(result1)  # Output: 49

height2 = [1, 1]
result2 = max_area_bruteforce(height2)
print(result2) # Output: 1

height3 = [4, 3, 2, 1, 4]
result3 = max_area_bruteforce(height3)
print(result3)  # Output: 16

Time Complexity:

The time complexity is O(n^2), where n is the length of the input array.

Space Complexity:

The space complexity is O(1) since no additional space is used.

Solution 2: Using Two Pointers

This solution uses a two-pointer approach to find the maximum area by calculating the width between the lines and the minimum height of the two lines. The pointers move towards each other to explore potentially larger areas.

from typing import List

def max_area(height: List[int]) -> int:
    """
    Return the maximum area of water that can be contained by two lines.

    Parameters:
    - height: List of non-negative integers representing the height of each line.

    Returns:
    - int: Maximum area of water.
    """
    max_area = 0
    left, right = 0, len(height) - 1

    while left < right:
        h = min(height[left], height[right])
        w = right - left
        max_area = max(max_area, h * w)

        # Move the pointers towards each other to explore potentially larger areas
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

# Example usage:
height1 = [1, 8, 6, 2, 5, 4, 8, 3, 7]
result1 = max_area(height1)
print(result1)  # Output: 49

height2 = [1, 1]
result2 = max_area(height2)
print(result2) # Output: 1

height3 = [4, 3, 2, 1, 4]
result3 = max_area(height3)
print(result3)  # Output: 16

Time Complexity:

Let’s break down the time complexity of the provided solution for the “Container With Most Water” problem.

  • The algorithm uses a two-pointer approach, where the pointers (left and right) start from the two ends of the array and move towards each other. The key insight is that to maximize the area, we need to consider the widest possible container, and the width is determined by the distance between the two pointers.

  • The main loop runs until the left pointer is equal to or greater than the right pointer. In each iteration, the algorithm calculates the area based on the minimum height between the two lines and the width, updates the max_area if needed, and then moves the pointers towards each other.

  • Since the pointers are always moving towards each other, and each pointer movement is done in constant time, the time complexity of this algorithm is O(n), where n is the length of the input array height. In the worst case, each element in the array is visited once, and the pointers traverse the entire array. Therefore, the overall time complexity is linear with respect to the size of the input array.

To summarize, the time complexity is O(n), where n is the length of the input array. It is more efficient than the brute-force approach.

Space Complexity:

The space complexity is O(1) since no additional space is used.