1. Problem statement

You are given an array height of length n, where each element represents the height of a vertical line drawn at that index i. These lines are drawn on the x-axis from (i, 0) to (i, height[i]).

You need to find two lines such that, together with the x-axis, they form a container that holds the maximum amount of water. Return the maximum water the container can store.

You cannot slant the container, so the container must be vertical.

Example:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

Explanation: The lines at index 1 (height 8) and index 8 (height 7) form the container with the largest area:
min(8,7) * (8 - 1) = 7 * 7 = 49

8 |     |                       |     
7 |     |                       |   | 
6 |     |       |               |   | 
5 |     |       |       |       |   | 
4 |     |       |       |   |   |   | 
3 |     |       |       |   |   |   | 
2 |     |       |   |   |   |   |   | 
1 | |   |   |   |   |   |   |   |   | 
0 +---------------------------------+
    0   1   2   3   4   5   6   7   8

2. Understanding the Problem

Each pair of lines can potentially form a container. The water that can be stored between any two lines is determined by:

Area = min(height[i], height[j]) * (j - i)

Where:

• min(height[i], height[j]) is the height of the container (limited by the shorter line),
• (j - i) is the width of the container (distance between the lines).

A brute-force approach would compare all pairs (i, j) with i < j, but this would take O(n²) time.

We need an efficient O(n) solution.

3. Example Walkthrough

Input:

height = [1,8,6,2,5,4,8,3,7]

Steps:

• left = 0, right = 8 → min(1, 7) * (8-0) = 1 * 8 = 8
• left = 1, right = 8 → min(8, 7) * (8-1) = 7 * 7 = 49 ← max so far
• Since 7 < 8, move right to 7 → min(8, 3) * (7-1) = 3 * 6 = 18
• Continue shrinking the pointers based on which height is shorter…
• Eventually, the max found is 49.

4. Java Solution

public class ContainerWithMostWater {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int left = 0;
        int right = height.length - 1;

        while (left < right) {
            // Height is the minimum of the two lines
            int currentHeight = Math.min(height[left], height[right]);
            // Width is the distance between the lines
            int width = right - left;
            // Calculate current area
            int area = currentHeight * width;
            // Update max area
            maxArea = Math.max(maxArea, area);

            // Move the pointer pointing to the shorter line
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
}

4. Time and Space Complexity

• Time Complexity: O(n)
  Only one pass through the array using two pointers.
• Space Complexity: O(1)
  No extra space is used.