Container with most water

In this problem, you are given an array of lines in which each element represents the height of the respective line. Lines are such that any two lines form a container.

The following figure shows the actual representation.

Find the two lines such that the container formed by these lines contains the most water and simply return the amount of water it can hold. Note that slanting of the container is not allowed.

Approach

The key insight here is that by starting with two pointers at the outermost lines (widest container), and iteratively moving the pointers toward each other while keeping track of the minimum height, we are effectively exploring various combinations to find the maximum water containment.

Algorithm

1. Initialize two pointers, left and right, at the beginning and end of the heightArray, respectively.
2. Initialize a variable max_area to keep track of the maximum water trapped, initially set to 0.
3. Enter a loop that continues as long as the left pointer is less than the right pointer. This loop is used to explore different combinations of line pairs.
4. Calculate the width of the container as the difference between the right and left pointers.
5. Calculate the height of the container as the minimum of the heights of the lines at the left and right pointers. The water level can only go as high as the shorter of the two lines.
6. Calculate the area of the container by multiplying the width and height.
7. Update max_area with the maximum of the current max_area and the calculated area.
8. Move the pointers: If the height of the line at the left pointer is less than the height of the line at the right pointer, increment the left pointer. If the height of the line at the left pointer is greater than the height of the line at the right pointer, decrement the right pointer. If the heights are equal, either increment the left pointer or decrement the right pointer, as it won't affect the result.
9. Continue the loop until the left pointer is less than the right pointer.
10. After the loop finishes, return the max_area, which represents the maximum amount of water that can be contained between the vertical lines in the heightArray.

Complexity

• Time Complexity: O(N), where N is the size of the array
• Space Complexity: O(1)

Code

#Java Code

public class ContainerWithMostWater {

    public int maxArea(int[] height) {
        int leftPointer = 0;
        int rightPointer = height.length - 1;
        int maxArea = 0;

        while (leftPointer < rightPointer) {
            int width = rightPointer - leftPointer;
            int minHeight = Math.min(height[leftPointer], height[rightPointer]);
            int area = minHeight * width;
            maxArea = Math.max(maxArea, area);

            if (height[leftPointer] < height[rightPointer]) {
                leftPointer++;
            } else if (height[leftPointer] > height[rightPointer]) {
                rightPointer--;
            } else {
                leftPointer++;
                rightPointer--;
            }
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int[] height = {13, 5, 2, 45, 20, 10, 34, 98, 27};
        ContainerWithMostWater container = new ContainerWithMostWater();
        System.out.println("Maximum water the container can hold: " + container.maxArea(height));
    }
}

Output

Maximum water the container can hold: 180