Problem: Container With Most Water (Medium)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

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. Return the maximum amount of water a container can store.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49 (Width between index 1 and 8 is 7. Height is min(8, 7) = 7. Area = 7*7 = 49).

2. The Mental Model: The "Bottleneck" Strategy

The area of a container is determined by two factors:

Width: The distance between the two vertical lines.
Height: The height of the shorter of the two lines.

Formula: Area = (RightIndex - LeftIndex) * min(height[Left], height[Right])

To maximize the area, we want to maximize both width and height. If we start with the maximum possible width (pointers at the extreme ends), how do we decide which pointer to move?

Since the width only decreases as we move pointers inward, the only way to find a larger area is to find a significantly taller line. Moving the taller line will never help because the area is still limited by the existing shorter line. Therefore, the only logical move is to discard the shorter line and move its pointer inward.

3. Visual Execution (Greedy Squeeze)

graph LR
    subgraph "Greedy Strategy"
        L[L: Height 8] --- R[R: Height 7]
        R -- Is shorter --> R_Move[Move R to Left]
        L1[L: Height 8] --- R1[R: Height 3]
        R1 -- Is shorter --> R1_Move[Move R to Left]
    end

4. Java Implementation (Optimal O(N))

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

    while (left < right) {
        // 1. Calculate current area
        int currentWidth = right - left;
        int currentHeight = Math.min(height[left], height[right]);
        int currentArea = currentWidth * currentHeight;
        
        // 2. Update global maximum
        maxArea = Math.max(maxArea, currentArea);

        // 3. The Greedy Choice: Discard the shorter line
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxArea;
}

5. Verbal Interview Script (Staff Tier)

Interviewer: "Why is moving the shorter line guaranteed to work?"

You: "This is a Greedy Two-Pointer approach. We start with the maximum possible width. In this initial state, the area is limited by the shorter line. If we move the taller line inward, the width decreases, and the height of the new container will either be even smaller or stay the same (limited by the original short line). Thus, the area can only decrease. The only chance to find a larger area is to move the shorter line in hopes of finding a much taller one that compensates for the loss in width. This pruning of the search space allows us to solve in $O(N)$ time instead of checking all $O(N^2)$ combinations."

6. Staff-Level Follow-Ups

Follow-up 1: "What if there are multiple lines of the same height?"

The Answer: "It doesn't matter which one we move first. Moving either (or both) inward is necessary because as long as both stay as the boundaries, the area cannot increase (width is decreasing and height is already at its max for that pair)."

Follow-up 2: "How does this relate to the Trapping Rain Water problem?"

The Answer: "While both use Two Pointers, the logic is different. Trapping Rain Water is about accumulating volume at every single index based on local boundaries. Container With Most Water is about finding the single global maximum area. However, both rely on the 'bottleneck' principle where the shorter wall dictates the state."

7. Performance Nuances (The Java Perspective)

Math.min overhead: In the extreme hot path of a tight loop, (a < b) ? a : b can be slightly faster than Math.min(a, b) due to how the JVM inlines these operations, though the difference is negligible for most interview scenarios.
Array Access: Modern CPUs use pre-fetching. Since we are accessing the array from both ends and moving towards the center, we have two sequential access streams which are very cache-friendly.

6. Staff-Level Verbal Masterclass (Communication)

Interviewer: "How would you defend this specific implementation in a production review?"

You: "In a mission-critical environment, I prioritize the Big-O efficiency of the primary data path, but I also focus on the Predictability of the system. In this implementation, I chose a iterative two-pointer approach. While a recursive solution is more readable, I would strictly monitor the stack depth. If this were to handle skewed inputs, I would immediately transition to an explicit stack on the heap to avoid a StackOverflowError. From a memory perspective, I leverage primitive arrays to ensure that we minimize the garbage collection pauses (Stop-the-world) that typically plague high-throughput Java applications."

7. Global Scale & Distributed Pivot

When a problem like this is moved from a single machine to a global distributed architecture, the constraints change fundamentally.

Data Partitioning: We would shard the input space using Consistent Hashing. This ensures that even if our dataset grows to petabytes, any single query only hits a small subset of our cluster, maintaining logarithmic lookup times.
State Consistency: For problems involving state updates (like DP or Caching), we would use a Distributed Consensus protocol like Raft or Paxos to ensure that all replicas agree on the final state, even in the event of a network partition (The P in CAP theorem).

8. Performance Nuances (The Staff Perspective)

Cache Locality: Accessing a 2D matrix in row-major order (reading [i][j] then [i][j+1]) is significantly faster than column-major order in modern CPUs due to L1/L2 cache pre-fetching. I always structure my loops to align with how the memory is physically laid out.
Autoboxing and Generics: In Java, using List<Integer> instead of int[] can be 3x slower due to the overhead of object headers and constant wrapping. For the most performance-sensitive sections of this algorithm, I advocate for primitive specialized structures.

Key Takeaways

The Answer: "It doesn't matter which one we move first. Moving either (or both) inward is necessary because as long as both stay as the boundaries, the area cannot increase (width is decreasing and height is already at its max for that pair)."
The Answer: "While both use Two Pointers, the logic is different. Trapping Rain Water is about accumulating volume at every single index based on local boundaries. Container With Most Water is about finding the single global maximum area. However, both rely on the 'bottleneck' principle where the shorter wall dictates the state."
MANG Problem #12: 3Sum (Squeeze Pattern)