Container With Most Water- Java Solution

1. Introduction

In this post, we'll explore a fascinating problem often encountered in coding interviews and algorithmic challenges: finding the container that can hold the most water, given a set of vertical lines. This problem is a classic example of using the two-pointer technique in an array to find an optimal solution.

Problem

We are provided with an integer array 'height' of length n, representing the heights of n vertical lines drawn on a plane. The challenge is to find two lines that, together with the x-axis, form a container that holds the maximum amount of water. It's important to note that the container cannot be slanted.

2. Solution Steps

1. Initialize two pointers: one at the start and another at the end of the array.

2. Calculate the area formed by the lines at the two pointers and the x-axis.

3. Update the maximum area found so far.

4. Move the pointer pointing to the shorter line towards the other pointer.

5. Repeat steps 2-4 until the two pointers meet.

6. Return the maximum area found.

3. Code Program

public class ContainerWithMostWater {
    public static void main(String[] args) {
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(maxArea(height)); // Test the function
    }

    // Function to find the maximum water that can be contained
    public static int maxArea(int[] height) {
        int maxArea = 0; // Store the maximum area found
        int left = 0; // Left pointer
        int right = height.length - 1; // Right pointer

        while (left < right) {
            int width = right - left; // Calculate width of the container
            int minHeight = Math.min(height[left], height[right]); // Find the shorter line
            maxArea = Math.max(maxArea, width * minHeight); // Update the maximum area

            // Move the pointer pointing to the shorter line
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea; // Return the maximum area found
    }
}

Output:

49

Explanation:

1. maxArea: This function employs a two-pointer approach, starting from the ends of the array.

2. At each step, it calculates the area formed by the container, defined by the lines at the two pointers and the x-axis.

3. It updates the maxArea if a larger area is found.

4. The pointers are moved towards each other, always moving the pointer at the shorter line, as this has the potential to increase the area.

5. The process repeats until the pointers meet, ensuring all possible containers are considered.

6. The function finally returns the maximum area found, which is the answer to the problem.