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 are at (i, ai) and (i, 0). Find two lines, which, together with the x-axis, forms a container that would hold the greatest amount of water. Return the maximum area of the water it can contain.

Function Signature:

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.
    """
    # Your code here

Example:

# Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
# Output: 49
# Explanation: The lines at index 1 and index 8 together with the x-axis form a container with an area of 7 * 7 = 49.

# Input: height = [1, 1]
# Output: 1

# Input: height = [4, 3, 2, 1, 4]
# Output: 16

Note:

  • You may not slant the container.

Instructions:

  • Write the max_area function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊