Leetcode | 11. Container With Most Water | 150 days of leetcode

 

Finding the Maximum Area of Water Container: A Beginner's Guide

Imagine you have an array of integers where each integer represents the height of vertical lines drawn on a graph. Your task is to find two lines that, along with the x-axis, form a container that holds the most water. This classic problem can be solved efficiently using a two-pointer approach. Let's dive in and solve it step-by-step.

Problem Statement

You are given an integer array height of length n. Each element in the array represents the height of a vertical line drawn from the x-axis at that index. You need to find two lines such that together with the x-axis, they form a container that holds the maximum amount of water.

Example

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49

Explanation: In this case, the maximum area of water the container can contain is 49. This is achieved by the lines at indices 1 and 8, with heights 8 and 7 respectively.

Steps to Solve the Problem

We will use a two-pointer technique to solve this problem efficiently.

Step 1: Initialize Two Pointers

We start with two pointers:

• left pointer at the beginning of the array (left = 0)
• right pointer at the end of the array (right = len(height) - 1)

Step 2: Calculate the Area

The area formed between the lines at the two pointers is determined by the shorter line. The formula for the area is:

Area = min(height[left], height[right]) * (right - left)

Step 3: Move the Pointers

To find a larger container, we move the pointer that points to the shorter line inward:

• If height[left] < height[right], move the left pointer one step to the right (left += 1)
• Otherwise, move the right pointer one step to the left (right -= 1)

We repeat these steps until the two pointers meet.

Python Code

Here's how you can implement this in Python:

def maxArea(height):
    left = 0
    right = len(height) - 1
    max_area = 0

    while left < right:
        # Calculate the current area
        current_area = min(height[left], height[right]) * (right - left)
        # Update max_area if the current area is larger
        max_area = max(max_area, current_area)

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

    return max_area

Example Usage

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

# Example 2
height = [1,1]
print(maxArea(height))  # Output: 1

Explanation of the Example

• Example 1: The maximum area is achieved between the lines at indices 1 and 8 (0-based), i.e., between heights 8 and 7. The width between these lines is 8 - 1 = 7. Thus, the area is min(8, 7) * 7 = 7 * 7 = 49.

• Example 2: The maximum area is 1, formed by the lines at indices 0 and 1. The height of both lines is 1, and the width is 1 - 0 = 1, so the area is min(1, 1) * 1 = 1.

Conclusion

This two-pointer technique allows us to efficiently solve the problem in O(n) time complexity, where n is the array's length. By always moving the pointer at the shorter line, we maximize the chance of finding a larger container, ensuring we find the maximum area.

With this approach, you can tackle the container problem confidently, even if you're just starting out in programming!