Container With Most Water LeetCode Problem 11 [Python Solution]

Let’s learn how to solve the Container With Most Water LeetCode problem efficiently with step-by-step approaches in Python together in this guide.

Problem Overview

Question: You are given an integer arrayheight 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.

…

In this problem, we are given an array called height representing the heights of vertical lines.

The goal is to find two lines that, along with the x-axis, form a container that can hold the most water.

The task is to determine the maximum amount of water that the container can store.

Example 1:

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

Example 2:

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

Problem Constraints

The length of the height array, denoted as ‘n’, is between 2 and 105.
The height of the vertical lines is between 0 and 104.

Container With Most Water LeetCode Problem Solution

1. Bruteforce Approach

The initial approach to solve this problem is to try every possible combination of two vertical lines as the left and right boundaries of the container and compute the area for each combination.

We will keep track of the maximum area found during this process.

Initialize a variable maxArea to store the maximum area found. Set it to 0.
Use two nested loops to iterate over all possible pairs of left and right boundaries. The outer loop iterates from left = 0 to left = n-2, and the inner loop iterates from right = left + 1 to right = n-1.
For each pair of boundaries (left, right), calculate the area by finding the minimum height between the two boundaries and multiplying it by the width (right – left).
Update maxArea with the maximum of its current value and the area calculated in step 3.
After both loops finish, maxArea will contain the maximum area, so return it as the result.

Here is the Python code for the brute-force approach:

def maxArea(height):
    maxArea = 0
    n = len(height)

    for left in range(n - 1):
        for right in range(left + 1, n):
            h = min(height[left], height[right])
            w = right - left
            area = h * w
            maxArea = max(maxArea, area)

    return maxArea

The time complexity of this brute-force approach is O(n^2), where 'n' is the length of the input array height.

It involves two nested loops to consider all possible pairs of boundaries.

2. Efficient Approach with Two Pointers

container with most water leetcode problem solution

The brute-force approach works but is not efficient, especially for large input arrays.

We can improve the time complexity by O(n) using a two-pointer approach.

Initialize two pointers, left and right, at the beginning and end of the height array, respectively.
Initialize a variable maxArea to store the maximum area found and set it to 0.
While the left pointer is less than the right pointer, calculate the area using the current heights at the left and right positions and the width between them (which is right - left).
Update maxArea with the maximum of its current value and the area calculated in step 3.
To maximize the area, move the pointer that points to the shorter vertical line towards the other pointer. This is because moving the pointer to the taller line would not change the height of the container but would reduce the width, resulting in a smaller area.
Repeat steps 3-5 until the left pointer is no longer less than the right pointer.
Finally, return maxArea as the result.

Here is the Python code for the efficient two-pointer approach:

View on GitHub ➹

def maxArea(self, height: List[int]) -> int:
    maxArea = 0
    left = 0
    right = len(height) - 1
    
    while left &lt; right:
        h = min(height[left], height[right])
        w = right - left
        area = h * w
        maxArea = max(maxArea, area)
        
        if height[left] &lt; height[right]:
            left += 1
        else:
            right -= 1
    
    return maxArea

This efficient approach reduces the time complexity to O(n) since we traverse the array only once with two-pointers.

We update the pointers based on the height of the vertical lines, ensuring that we always move the pointer pointing to the shorter line.

Reasoning Behind Our Efficient Approach

The efficient approach relies on the observation that the maximum area of a container is determined by the height of the shorter vertical line and the width between the lines.

By starting with the widest possible width (with the two pointers at the beginning and end of the array), we can guarantee that any movement of the pointers toward each other will either keep the width the same or decrease it.

Therefore, to maximize the area, we must move the pointer pointing to the shorter line.

This ensures that we explore all possible combinations without redundancy and in linear time.

Conclusion

In this blog post, we tackled the Container With Most Water problem on LeetCode.

We explored both a brute-force approach and an efficient two-pointer approach to find the maximum water container.

While the brute-force approach involves nested loops and has a time complexity of O(n^2), the efficient approach optimizes the solution to run in O(n) time.

By carefully selecting the boundaries and moving the pointers strategically, we can maximize the area of the container while traversing the array only once.

When faced with this problem in an interview or a coding challenge, the efficient two-pointer approach is the recommended solution due to its superior time complexity.

It showcases a valuable problem-solving technique that can be applied to similar problems where optimizing the use of two-pointers can significantly improve efficiency.

So, keep this approach in your toolkit for future algorithmic challenges! If you have any questions, suggestions, or thoughts about this problem or its solutions, please feel free to comment below.

Happy coding!