Problem: Container With Most Water

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Approach: Two Pointers (Greedy)

The area of the container is limited by the shorter line. $Area = \text{width} \times \min(height[left], height[right])$

1. Initialize: left = 0, right = n - 1.
2. Calculate Area: Compute area and update maxArea.
3. Move Pointer: To find a potentially larger area, move the pointer that points to the shorter line.
   • Why? Because if we move the longer line, the width decreases, but the height is still limited by the same short line (or an even shorter one). The only way to increase the height is to find a line taller than the current short one.

Java Implementation

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

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

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

Dry Run

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

Final Result: 49.

Complexity Discussion

• Time Complexity: $O(n)$.
• Space Complexity: $O(1)$.

Interview Tips

• This problem is a mix of Two Pointers and Greedy logic.
• Clearly explain why moving the taller line is useless.