Coding Problem: Container With Most Water

Problem Statement

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Solution Explanation

The problem is asking to find two lines from the given array which can trap the maximum amount of water. The amount of water trapped by any two lines is not just dependent on the height of the shorter line but also on the distance between them.

We can use a two-pointer approach to solve this problem. We start with two pointers, one at the beginning and one at the end of the array constituting the length of the lines. Filling water up to the brim of the shorter line will give us the amount of water that can be stored between those two lines. We can keep track of the maximum area of water stored. Then, we move the pointer pointing to the shorter line towards the other end by one step.

Pseudocode

Initialize left pointer to 0 and right pointer to length of the array - 1

Initialize maxArea to 0

While left pointer is less than right pointer

    Calculate the height as the minimum of the height at the left pointer and the height at the right pointer

    Calculate the width as the difference between the right pointer and the left pointer

    Calculate the area as height * width

    If area is greater than maxArea, update maxArea

    If height at the left pointer is less than height at the right pointer, increment the left pointer, else decrement the right pointer

Return maxArea

Code

Here is the Python code for the problem:

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

    while left < right:
        h = min(height[left], height[right])
        w = right - left
        area = h * w

        if area > maxArea:
            maxArea = area

        if height[left] < height[right]:
            left += 1

        else:
            right -= 1

    return maxArea

Important Notes

• The two-pointer approach is a common technique used for array traversal in many problems. It is especially useful when you need to compare elements from the beginning and end of the array.
• In this problem, we always move the pointer pointing to the shorter line because moving the pointer pointing to the taller line wouldn't help increase the area. The height of the area is limited by the height of the shorter line, and moving the pointer pointing to the taller line would only decrease the width without increasing the height.
• The time complexity of this solution is O(n), where n is the length of the array. The space complexity is O(1), as no extra space is used.