Container With Most Water medium

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

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

Steps

The problem is to find the maximum area formed by two lines and the x-axis. The area is calculated as width * min(height1, height2), where width is the distance between the two lines and height1 and height2 are the heights of the two lines.

A naive approach would be to check all possible pairs of lines, which results in O(n^2) time complexity. However, we can optimize this using a two-pointer approach.

1. Initialization: Use two pointers, left and right, pointing to the beginning and end of the height array, respectively.
2. Iteration: Iterate while left < right.
3. Area Calculation: Calculate the area for the current pair of lines: area = (right - left) * min(height[left], height[right]). Update the maximum area found so far.
4. Pointer Movement: Move the pointer with the shorter height inwards. This is because if we move the pointer with the taller height, the width will decrease, and the area can only potentially decrease (since the height will not increase). Moving the shorter height allows for the potential of finding a larger area with a greater height.
5. Return: After the loop completes, return the maximum area found.

Explanation

The key insight is that moving the pointer associated with the shorter bar is the only way to potentially increase the area. If we move the taller bar, the width will decrease, and since the height will only possibly get smaller or stay the same, the area will only get smaller or stay the same.

Code

def maxArea(height):
    """
    Finds the maximum area that can be formed by two lines and the x-axis.

    Args:
        height: A list of integers representing the heights of the lines.

    Returns:
        The maximum area.
    """
    max_area = 0
    left = 0
    right = len(height) - 1

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

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

    return max_area

Complexity

• Time Complexity: O(n), where n is the length of the height array. We iterate through the array at most once using the two-pointer approach.
• Space Complexity: O(1). We only use a few variables to store the maximum area, left and right pointers, and the current area. The space used is constant regardless of the input size.