Problem Informations

• Problem Index: 11
• Problem Link: Container With Most Water
• Topics: Array, Two Pointers, Greedy

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 $i^{th}$ line are $(i, 0)$ and $(i, \text{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

Constraints:

• $n == \text{height.length}$
• $2 \leq n \leq 10^5$
• $0 \leq \text{height}[i] \leq 10^4$

Intuition

The problem of finding the maximum area that can be formed between vertical lines on a plane can be tackled efficiently by observing that the area is determined by the shorter of the two lines and the distance between them. Thus, to maximize the area, we should aim to maximize both the height and the distance. The naive approach would involve checking all possible pairs of lines, but since this would be computationally expensive, a more efficient method involves using a two-pointer technique where we adjust the pointers based on the relative heights of the lines currently being considered.

Approach

The approach adopts a two-pointer technique to efficiently compute the maximum area. Both pointers are initialized at the extreme ends of the height array, representing the initial pair of lines. The algorithm proceeds as follows:

1. Initialize Maximum Area: Begin with maxWater set to zero, which will hold the maximum area found during the iteration.

2. Two-Pointer Technique:

   • Set left pointer at the start (index 0) and right pointer at the end (index n-1, where n is the length of the height array).

3. Calculate and Compare Areas:

   • While the left pointer is less than the right pointer:
     • Compute the potential area formed by the lines at left and right using the formula: $$ \text{Area} = (\text{right} - \text{left}) \times \min(\text{height}[left], \text{height}[right]) $$
     • Compare this area with maxWater and update maxWater if the new area is larger.

4. Pointer Adjustment:

   • Move the pointer corresponding to the shorter line:
     • If height[left] < height[right], increment the left pointer to explore potentially taller lines on the right side.
     • If height[left] > height[right], decrement the right pointer to explore potentially taller lines on the left side.
     • If the lines are of equal height, increment both pointers to cover new ground as any movement could lead to a potentially greater area.

5. Termination: Continue the process until the left pointer meets or surpasses the right pointer, indicating all possible container configurations have been evaluated.

6. Result: Once the loop concludes, maxWater contains the maximum area found, which is then returned.

By iteratively evaluating areas in this manner and strategically shifting the pointers, the algorithm achieves an optimal time complexity of $O(n)$, where $n$ is the number of vertical lines. This efficiency is crucial given the constraint that $n$ can be as large as $10^5$.

Code

C++

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxWater = 0;  // Initialize the maximum water storage
        int left = 0;  // Start pointer at the beginning of the array
        int right = height.size() - 1;  // End pointer at the end of the array

        // Iterate while the left pointer is less than the right pointer
        while (left < right) {
            // Calculate the area with the current boundaries and update maxWater
            maxWater = max(maxWater, 
                           (right - left) * min(height[left], height[right]));

            // Move the pointer pointing to the shorter line
            if (height[left] < height[right]) {
                left++;  // Move left pointer to the right
            } else if (height[left] > height[right]) {
                right--;  // Move right pointer to the left
            } else {
                // If both lines are of the same height, move both pointers
                left++;
                right--;
            }
        }

        return maxWater;  // Return the maximum water area found
    }
};

Python

class Solution:
    def maxArea(self, height):
        maxWater = 0  # Initialize the maximum water storage
        left = 0  # Start pointer at the beginning of the array
        right = len(height) - 1  # End pointer at the end of the array

        # Iterate while the left pointer is less than the right pointer
        while left < right:
            # Calculate the area with the current boundaries and update maxWater
            maxWater = max(maxWater, 
                           (right - left) * min(height[left], height[right]))

            # Move the pointer pointing to the shorter line
            if height[left] < height[right]:
                left += 1  # Move left pointer to the right
            elif height[left] > height[right]:
                right -= 1  # Move right pointer to the left
            else:
                # If both lines are of the same height, move both pointers
                left += 1
                right -= 1

        return maxWater  # Return the maximum water area found

Complexity

• Time complexity: $O(n)$

The algorithm uses a two-pointer approach, where one pointer starts at the beginning and the other starts at the end of the array. In each iteration, at least one of the pointers is moved toward the other pointer. Since there are $n$ elements in the array and each element is visited at most once by either the left or the right pointer, the time complexity of this approach is $O(n)$.

• Space complexity: $O(1)$

The algorithm only uses a constant amount of extra space aside from the input, primarily to store variables like maxWater, left, and right. The space used does not depend on the size of the input array, so the space complexity is $O(1)$.