11. Container With Most Water#

Difficulty: Medium

Link to Problem: To see the Container With Most Water problem on LeetCode, click here!

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the \(i^{th}\) 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.

Constraints:

  • n == height.length

  • 2 <= n <= \(10^5\)

  • 0 <= height[i] <= \(10^4\)

Solution:#

Here’s a Python function to solve this problem:

def maxArea(height):
    # Initialize the maximum area to 0.
    max_area = 0
    # Initialize two pointers, one at the beginning (left) and one at the end (right) of the array.
    left = 0
    right = len(height) - 1

    # Iterate until the left pointer is less than the right pointer.
    while left < right:
        # Calculate the height of the container, which is the minimum height of the two lines.
        h = min(height[left], height[right])
        # Calculate the width of the container, which is the distance between the two pointers.
        width = right - left
        # Calculate the area of the container using height and width and update max_area if it's greater.
        max_area = max(max_area, h * width)

        # Move the pointer with the shorter line inward.
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    # Continue this process until left < right, and then return the maximum area.
    return max_area

Explanation:#

  1. We start with initializing max_area to 0, which will store the maximum area of water that can be contained by the lines.

  2. Two pointers, left and right, are initialized to the beginning and end of the input height array.

  3. The main loop runs while left is less than right. This ensures that we are checking all possible pairs of lines in a systematic way.

  4. Inside the loop:

    • We calculate the height of the container h as the minimum of the heights at the left and right pointers. This represents the height of the water the container can hold.

    • We calculate the width of the container as the difference between right and left. This represents the distance between the two lines.

    • We calculate the area of the container using h * width and update max_area if the calculated area is greater than the current max_area.

  5. After calculating the area and updating max_area, we move one of the pointers. We move the pointer pointing to the shorter line inward because moving the pointer pointing to the taller line won’t increase the height and will only decrease the width, which will result in a smaller area.

  6. We continue this process until left is no longer less than right, indicating that we have checked all possible pairs of lines.

  7. Finally, we return the max_area which contains the maximum area of water that can be contained by two lines from the input array.

Test cases#

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

Output: 49

# Example 2
height2 = [1, 1]
result2 = maxArea(height2)
print("Output:", result2)

Output: 1

# Additional Example
height3 = [3, 9, 3, 4, 7, 2, 12, 6]
result3 = maxArea(height3)
print("Output:", result3)

Output: 45

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the maxArea function:

Time Complexity: The function uses a two-pointer approach to find the maximum area of water. In the worst case, both the left and right pointers traverse the entire input array once. Therefore, the time complexity is O(n), where n is the number of elements in the height array.

Space Complexity: The function uses a constant amount of extra space for variables like max_area, left, right, h, and width. It does not use any data structures whose space consumption depends on the input size. As a result, the space complexity is O(1), which means it has constant space complexity.

In summary, the maxArea function has a time complexity of O(n) and a space complexity of O(1), making it an efficient algorithm for finding the maximum area of water that can be contained by two lines in the input array.

Challenging Exercises:#

  1. Optimization Challenge: Modify the maxArea function to not only return the maximum area but also the indices of the two lines that form the container with the maximum area.

  2. Variant Problem: Instead of finding the maximum area of water, find the minimum amount of water required to fill all the gaps between the lines. You’ll need to return the total water volume needed.