4. Container With Most Water

Problem Description

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

Example 2:

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

Intuition

The width between two lines decreases as we move inward, so to maximize the area, we must consider both width and height. A two-pointer approach allows us to adjust height and width optimally.

Solution Approach

1. Start with two pointers at both ends of the array.
2. Calculate the area between the two pointers.
3. Move the pointer pointing to the shorter line inward (to possibly get a taller line).
4. Repeat until the pointers meet.

Example Walkthrough

Example 1:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Example 2:
Input: [1,1]
Output: 1

Solution Implementation

class Solution:
    def maxArea(self, height):
        left, right = 0, len(height) - 1
        max_area = 0
        while left < right:
            width = right - left
            area = min(height[left], height[right]) * width
            max_area = max(max_area, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)