The Container With Most Water problem and solution in Java and Python

The Container With Most Water problem is a classic DSA (Data Structures & Algorithms) question based on the two-pointer technique, and it’s a favorite in FAANG interviews.

Let’s go step by step 👇

---

🧩 Problem Statement

You are given an array height[], where each element represents the height of a vertical line drawn on the x-axis.

The goal is to find two lines that together form a container, holding the maximum amount of water. The container’s area is determined by the distance between the two lines (width) and the height of the shorter line.

Example:

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

Explanation:

• The max area is between lines at indices 1 and 8 → min(8,7) * (8-1) = 7 * 7 = 49

---

📉 Brute Force Approach (O(n²))

Try every pair (i, j) and calculate the area:

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

Keep track of the maximum.

Java (Brute Force)

public class ContainerMostWater {
    public static int maxArea(int[] height) {
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int area = Math.min(height[i], height[j]) * (j - i);
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }

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

---

⚡ Optimized Approach (O(n)) — Two Pointer Technique

Idea:

Start with two pointers at both ends of the array:

• left = 0, right = n-1

• Compute area:

  area = min(height[left], height[right]) * (right - left)
  

• Move the pointer at the shorter line inward:

  • If height[left] < height[right], move left++
  • Else move right--

• Repeat until left >= right

This works because the area is limited by the shorter height, and moving the taller side inward cannot increase area.

---

✅ Java Solution (Optimal)

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

        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, area);

            if (height[left] < height[right])
                left++;
            else
                right--;
        }

        return maxArea;
    }

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

---

✅ Python Solution (Optimal)

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

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

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

    return max_area

# Example
print(maxArea([1,8,6,2,5,4,8,3,7]))  # Output: 49

---

🧠 Complexity Analysis

Type	Complexity
Time Complexity	O(n)
Space Complexity	O(1)
Technique	Two Pointers

---

🔹 Why Two-Pointer Works

• Moving the shorter line might increase area, since height could increase.
• Moving the taller line can’t help — width decreases, and height can’t increase beyond the shorter line’s height.
• So, we skip impossible combinations in one linear pass.

---

📊 Visualization (Conceptually)

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

Left  -> height[1] = 8
Right -> height[8] = 7
Width = 7, Height = 7
Area = 7 * 7 = 49  ✅

---

💡 Variations

1. Trapping Rain Water Problem – similar use of two pointers, but adds trapped water calculation.
2. Max Water Between K Lines – extension of this concept.
3. Histogram Problems – often use similar area or height-width reasoning.

---