Leetcode 11 - Container With Most Water

Table of contents

Problem

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]).

Your task is to find two lines that, together with the x-axis, form a container that can store the maximum amount of water.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The max area of water (blue section) the container can contain is 49.

Example 2:

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

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Explanation/Approach

The problem is to maximize the area between two lines, which is determined by the shorter line and the distance between the lines. We use a two-pointer approach, starting from the ends of the array and moving towards the center. This approach ensures that we do not miss any potential larger area.

• Two-Pointers Approach: Initialize two pointers at both ends of the array. The area is calculated by the shorter of the two lines multiplied by the distance between them. Move the pointer at the shorter line towards the other pointer, as moving the longer line would not increase the area.

Solution: Two-Pointers Approach

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # Initialize two pointers and max_area variable
        left, right = 0, len(height) - 1
        max_area = 0

        # Iterate while left pointer is less than right pointer
        while left < right:
            # Calculate the current area
            width = right - left
            current_area = min(height[left], height[right]) * width
            max_area = max(max_area, current_area)

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

        return max_area

Time and Memory Complexity

The time complexity is O(n) as we traverse the array once using two pointers. The space complexity is O(1) as no additional space is required.

Explanation

The solution uses two pointers to explore every possible pair of lines in a single pass. By always moving the pointer at the shorter line, we ensure that we do not miss any larger area that could be formed by other pairs of lines. The height is equal as the shorter height of the 2 pointers, the width is equal to right - left pointer index.

Visualization

Iteration 1:
Array: [1,8,6,2,5,4,8,3,7]
        ↑               ↑
Calculation: Width = 8, Height = 1, Area = 8

Iteration 2:
Array: [1,8,6,2,5,4,8,3,7]
          ↑             ↑
Array[1] = 8, Array[8] = 7
Calculation: Width = 7, Height = 7, Area = 49

Iteration 3:
Array: [1,8,6,2,5,4,8,3,7]
          ↑           ↑
Array[1] = 8, Array[7] = 3
Calculation: Width = 6, Height = 3, Area = 18

...

Maximum Area Found: 49

In this case, the maximum area is 49, formed by the second (height = 8) and last (height = 7) lines.