Container With Most Water Algorithm Solution

The container with most water problem requires finding the maximum area formed between vertical lines, which can be efficiently solved using the two-pointer approach to achieve linear time complexity.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What are the constraints on the input array size? (e.g., is it up to 10⁵ elements?)
2. Are duplicate heights allowed in the input array?
3. Should I return the indices of the containers or just the maximum area?
4. Can I mutate the input array during processing?
5. What is the target time complexity for follow-up? (e.g., O(n) is preferred over O(n²))

Restatement of the pattern:
The Container with Most Water problem asks us to find two vertical lines from an array such that the area formed between them (with the x-axis) is maximized. The area is calculated as min(height[i], height[j]) * (j - i), where i and j are indices of the two lines.

Signal words and constraint shape:
Key indicators include "maximize area", "two pointers", "heights on x-axis", and a constraint that the water container must be formed between two vertical lines. The problem involves optimizing over pairs of indices with a mathematical relationship between their positions and values.

Assumptions made:

• The input array contains only non-negative integers (heights).
• We are looking for the maximum area between any two lines.
• The solution does not require returning indices, but rather just the maximum area value.

Scenario fit:
This is a classic static optimization problem where all input data is known upfront. It's not streaming or online because we have full access to the array and can process it in one pass.

This pattern is best solved using a two-pointer technique, which efficiently explores the search space by maintaining invariants and reducing redundant comparisons.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Container" or "area" maximization problems
• Two ends or boundaries that can be adjusted
• Arrays or lists where elements have numeric values (heights, weights, etc.)
• Need to find optimal pair of indices or elements

Why this pattern fits better than alternatives: This is a classic two-pointer technique problem where we're looking to maximize area between two lines. Unlike brute force approaches that check all pairs (O(n²)), the two-pointer approach leverages the fact that if we fix one pointer and move the other, we can make informed decisions about which direction to move based on height comparisons. This is more efficient than sliding window or greedy approaches for this specific constraint structure.

Conditions where variations apply:

• If the problem involves multiple dimensions or complex shapes, it might require computational geometry approaches
• For dynamic input streams where elements are added/removed, a different streaming algorithm might be needed
• If we're looking for minimum instead of maximum area, the logic would reverse

Core insight: The key insight is that we can eliminate suboptimal search space by always moving the pointer with smaller height. Since area is determined by width × min(height1, height2), if we move the taller line inward, we can never increase the area regardless of its new height. Therefore, moving the shorter line is always a better choice to potentially find a larger area.

This pattern works because it maintains the invariant that we're always considering the maximum possible area for each height, allowing us to prune branches efficiently.

3. Approach Evolution

Interview communication script:

"My first instinct is to use a brute force approach where I check every possible pair of lines to calculate the area, because that would give me the maximum area. But that's O(n²) time complexity because I'd have to check all pairs of lines. Let me think about how to optimize this...

I notice that if I sort the lines by their height, I can't just use that directly because the width matters too. But what if I think about this differently?

I notice that for any two lines, the area is determined by: min(height[i], height[j]) * (j - i). The key insight is that if I start with the widest possible container (leftmost and rightmost lines), and then move inward, I can make an informed decision about which pointer to move.

If the left line is shorter than the right line, moving the right pointer inward won't help me find a larger area because the width is decreasing and the height is bounded by the shorter left line. So I should move the pointer at the shorter line inward to try to find a taller line.

This is a two-pointer approach that maintains an invariant: at each step, I'm considering the best possible container that includes one of the current endpoints. This reduces the problem to O(n) time complexity by avoiding redundant calculations.

The key optimization is that I don't need to check all pairs - I can greedily move the pointer at the shorter line inward, because any container that includes that shorter line and a wider width will have area bounded by the shorter line's height."

Brute-force approach:

• Check every pair of lines (i,j) where i < j
• For each pair, calculate area = min(height[i], height[j]) * (j - i)
• Keep track of maximum area found
• Time complexity: O(n²), Space complexity: O(1)
• Not ideal because it's inefficient for large inputs and doesn't leverage the geometric constraints

Improved approach - Two-pointer technique:

• Start with left pointer at 0 and right pointer at n-1 (maximum width)
• At each step, calculate area = min(height[left], height[right]) * (right - left)
• Move the pointer at the shorter line inward
• Continue until pointers meet
• Time complexity: O(n), Space complexity: O(1)
• Key optimization: The greedy choice of moving the shorter line is mathematically sound because we can never improve upon a container that includes the shorter line with wider width

Final approach reasoning: The algorithm works because at each step, we're making a locally optimal choice that leads to global optimality. When we have the widest container, any container that includes the shorter of the two current lines will have area bounded by that line's height. So we can safely discard the shorter line and move inward, maintaining the invariant that we're always considering the best possible container that includes one of our current endpoints.

Important invariants:

1. The pointers always maintain a valid range (left < right)
2. At each step, we're considering the maximum area that includes one of our current endpoints
3. We never consider containers that we know are suboptimal due to width constraints

4. Data Structure Choice

For the Container with Most Water problem, the primary data structure is a two-pointer approach using integer indices to traverse the input array.

Primary Data Structures Used

1. Array/ArrayList of integers - The input height array is the primary data structure that holds the water container heights. This is the only data structure we need to store and access.

2. Integer variables (left, right) - Two pointers that serve as indices to track the current left and right boundaries of the container being evaluated.

Why Each Data Structure Is Needed

The array is essential because it contains the actual height values that determine container capacity. The two integer pointers are critical for implementing the optimal two-pointer algorithm, allowing us to efficiently explore candidate containers without checking all possible pairs.

Time and Space Impact

• Time Complexity: O(1) for pointer operations, O(n) overall for traversal
• Space Complexity: O(1) additional space (just two integer variables)
• The array itself is the input and doesn't count toward auxiliary space

Helper Structure Considerations

No additional helper structures are needed for the optimal solution. The two-pointer approach works directly with the input array indices, making it memory-efficient and clean.

The simplicity of using just two integer pointers is the key strength - it avoids any overhead from hash maps, stacks, or other complex data structures that would be unnecessary for this specific optimization problem.

5. Algorithm Walkthrough

Let me trace through the two-pointer approach with a concrete example:

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

Step 1: Initialize pointers - left = 0, right = 8

• Area = min(1,7) × (8-0) = 1 × 8 = 8
• Max area = 8

Step 2: Move shorter pointer - height[0] = 1 < height[8] = 7, so move left

• left = 1, right = 8
• Area = min(8,7) × (8-1) = 7 × 7 = 49
• Max area = 49

Step 3: Move shorter pointer - height[1] = 8 > height[8] = 7, so move right

• left = 1, right = 7
• Area = min(8,3) × (7-1) = 3 × 6 = 18
• Max area = 49

Step 4: Move shorter pointer - height[1] = 8 > height[7] = 3, so move right

• left = 1, right = 6
• Area = min(8,8) × (6-1) = 8 × 5 = 40
• Max area = 49

Step 5: Move shorter pointer - height[1] = 8 = height[6] = 8, move either (let's move right)

• left = 1, right = 5
• Area = min(8,4) × (5-1) = 4 × 4 = 16
• Max area = 49

Step 6: Move shorter pointer - height[1] = 8 > height[5] = 4, so move right

• left = 1, right = 4
• Area = min(8,5) × (4-1) = 5 × 3 = 15
• Max area = 49

Step 7: Move shorter pointer - height[1] = 8 > height[4] = 5, so move right

• left = 1, right = 3
• Area = min(8,2) × (3-1) = 2 × 2 = 4
• Max area = 49

Step 8: Move shorter pointer - height[1] = 8 > height[3] = 2, so move right

• left = 1, right = 2
• Area = min(8,6) × (2-1) = 6 × 1 = 6
• Max area = 49

Step 9: Move shorter pointer - height[1] = 8 > height[2] = 6, so move right

• left = 1, right = 1
• Loop terminates

The algorithm correctly identifies the maximum area of 49 at indices 1 and 8.

Key observations:

• We always move the pointer with smaller height because moving the taller one can only decrease the area
• The algorithm explores all possible configurations that could yield a better solution
• At each step, we maintain the invariant that we haven't missed any better solution

The termination condition is when left >= right, ensuring all valid combinations are considered.

6. Java Solution

public class ContainerWithMostWater {
    /**
     * Finds the maximum area of water that can be stored between two lines.
     * Uses two-pointer technique to achieve O(n) time complexity.
     * 
     * @param height Array of integers representing vertical lines
     * @return Maximum area of water that can be stored
     */
    public int maxArea(int[] height) {
        // Handle edge case of null or insufficient input
        if (height == null || height.length < 2) {
            return 0;
        }
        
        int left = 0;           // Left pointer starting from beginning
        int right = height.length - 1;  // Right pointer starting from end
        int maxArea = 0;        // Track maximum area found
        
        // Continue while pointers haven't met
        while (left < right) {
            // Calculate current area: width * min(height[left], height[right])
            int width = right - left;
            int currentHeight = Math.min(height[left], height[right]);
            int currentArea = width * currentHeight;
            
            // Update maximum area if current is larger
            maxArea = Math.max(maxArea, currentArea);
            
            // Move the pointer with smaller height inward
            // This is the key optimization - we can safely discard the shorter line
            if (height[left] < height[right]) {
                left++;  // Move left pointer inward
            } else {
                right--; // Move right pointer inward
            }
        }
        
        return maxArea;
    }
}

This solution implements the optimal two-pointer approach for the Container With Most Water problem. The key insight is that we always move the pointer pointing to the shorter line inward, as this gives us the potential for a larger area. The algorithm efficiently explores all possible configurations in linear time without needing to check every pair of lines.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm uses the two-pointer technique where each pointer moves toward the center at most once. Since we process each element at most once, the time complexity is linear in the size of the input array.

Space Complexity: O(1)

The solution only uses a constant amount of extra space for the two pointers and the maximum area tracking variable. No additional data structures grow with input size, making it space-efficient.

Why These Bounds Are Correct:

The key insight is that the two-pointer approach guarantees each element is visited at most once. At each step, we move either the left or right pointer inward based on which height is smaller. This ensures that we never revisit elements and the total number of operations equals the array length.

Optimality:

This solution is optimal for the problem since we must examine each element at least once to determine the maximum area, and the two-pointer technique achieves this minimal linear scan. Any algorithm solving this problem must have at least O(n) time complexity, making our solution asymptotically optimal.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Should return 0 as no container can be formed
• Single element: Cannot form a container, so return 0
• Two elements: Should return the area formed by the two elements (minimum height × 1)

Duplicate Values and Repeated States

• Arrays with many duplicate heights can cause confusion in algorithm logic
• The two-pointer approach correctly handles duplicates by moving the pointer with smaller height, regardless of whether it's a duplicate

Boundary Conditions

• Zero heights: If any height is zero, the area will be zero for that container
• Maximum integer values: Very large height values can cause overflow in area calculations (though Java's long handles this well)
• Large input sizes: Array size up to 10⁵ is manageable with O(n) approach

Common Implementation Mistakes

• Incorrect area calculation: Using min(height[left], height[right]) * (right - left) instead of proper width calculation
• Pointer movement logic: Moving the pointer with greater height instead of smaller height, which can skip optimal solutions
• Off-by-one errors: Not properly handling the case where pointers meet or when one pointer is at array bounds
• Not handling edge cases: Failing to check for null or empty arrays before processing

Key Implementation Notes

• Always validate input array is not null or empty before processing
• The algorithm assumes all heights are non-negative integers (as per problem constraints)
• When both pointers point to the same index, no container can be formed, so we stop when left >= right

9. Alternative Approaches

There are several alternative approaches to solving the Container with Most Water problem, each with different trade-offs:

Brute Force Approach: Check all possible pairs of lines to calculate the area. For each pair (i,j) where i < j, compute area = min(height[i], height[j]) * (j - i). This is O(n²) time and O(1) space. While simple to understand, it's inefficient for large inputs and doesn't leverage the key insight about optimal search direction.

Binary Search Approach: This is less intuitive but can work by treating the problem as finding maximum area under constraints. However, it's not a clean application of binary search and would require complex logic to maintain the water container constraints, making it more complicated than necessary.

Divide and Conquer: Split the array into halves and recursively find maximum areas in each half, plus the maximum area that crosses the midpoint. This approach has O(n log n) time complexity and is more complex to implement correctly, especially handling the cross-boundary cases.

Two-Pointer with Sorting: Create a copy of indices sorted by height values and use two pointers to traverse from both ends. This approach is O(n log n) due to sorting and doesn't maintain the original array order, which is unnecessary for this problem.

The chosen two-pointer approach is superior because it's O(n) time with O(1) space, directly exploits the problem structure where we can safely eliminate one side at each step, and is conceptually clean with a simple termination condition. The alternatives either increase time complexity or add unnecessary computational overhead without providing significant benefits for this specific problem structure.

10. Test Cases

public class ContainerWithMostWater {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        
        while (left < right) {
            // Calculate area with current pointers
            int currentHeight = Math.min(height[left], height[right]);
            int currentWidth = right - left;
            int currentArea = currentHeight * currentWidth;
            
            maxArea = Math.max(maxArea, currentArea);
            
            // Move the pointer with smaller height
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }
}

Sample Test Cases

Example 1:
Input: [1,8,6,2,5,4,8,3,7]
Expected Output: 49
Explanation: The max area is formed by indices 1 and 8, with height 8 and 7 respectively, giving area = min(8,7) × (8-1) = 7 × 7 = 49.

Example 2:
Input: [1,1]
Expected Output: 1
Explanation: Only two elements form a container with area = min(1,1) × (1-0) = 1 × 1 = 1.

Example 3:
Input: [4,3,2,1,4]
Expected Output: 16
Explanation: The max area is formed by indices 0 and 4, with height 4 and 4 respectively, giving area = min(4,4) × (4-0) = 4 × 4 = 16.

Tricky Case - All Same Heights:
Input: [5,5,5,5,5]
Expected Output: 20
Explanation: All elements have same height 5, so optimal area is min(5,5) × (4-0) = 5 × 4 = 20.

Boundary Case - Empty Array:
Input: []
Expected Output: 0
Note: This case should be handled by the constraints that guarantee at least 2 elements, but good to understand edge behavior.

Edge Case - Large Values:
Input: [1000000, 1000000]
Expected Output: 1000000
Explanation: Large values should still work with the algorithm as long as integer overflow is not a concern in the specific implementation context.

11. Final Summary

The core idea is to use the two-pointer technique to efficiently find the maximum area between vertical lines, achieving optimal O(n) time complexity by greedily eliminating suboptimal candidates. This solution works because moving the shorter of the two pointers inward can only lead to larger areas, while moving the taller one can only decrease the area. The approach is optimal for this problem as it avoids the O(n²) brute force method by leveraging the geometric properties of the area calculation and maintaining a key invariant that maximizes the base while considering height constraints.