Container With Most Water Algorithm Solution

The container with most water problem asks us to find the maximum area formed between two vertical lines in an array, where each element represents a vertical line's height. This classic algorithmic challenge demonstrates the power of the two-pointer technique for optimal solutions.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we mutate the input array, or must we preserve it?
2. What's the expected time complexity constraint? O(n) is optimal, but what's the target?
3. Are there any constraints on input size (e.g., max array length)?
4. Should we return the indices of the containers or just the maximum area?
5. How should we handle edge cases like empty input or arrays with fewer than 2 elements?

Restated problem: Given an array of integers representing vertical lines, find two lines that together with the x-axis form a container that holds the most water. The area is calculated as min(height[i], height[j]) * (j - i).

Input/Output:

• Input: Integer array height where height[i] represents the height of line at index i
• Output: Integer representing maximum area (water capacity) that can be contained

Constraints:

• Array length: 2 ≤ n ≤ 10⁵
• Each height value: 0 ≤ height[i] ≤ 10⁴
• We want the maximum area, not necessarily the actual container dimensions

Assumptions:

• The array is 0-indexed
• We can only form containers between two lines (not including the x-axis as a line)
• A container is formed by choosing any two elements from the array

Data shape and hidden structure: The problem involves a 2D geometric interpretation where we're looking for the maximum area rectangle that can be formed between two vertical lines. The key insight is that we're not just looking for the maximum height, but rather the optimal combination of height and width. The constraint that we can only choose two lines creates a combinatorial optimization problem where we must balance both dimensions.

This is fundamentally about finding the optimal trade-off between height and width in a constrained optimization setting.

2. Pattern Recognition

The problem exhibits the Two Pointers pattern, which is commonly used for optimization problems involving arrays or lists where we need to find optimal pairs or subarrays.

The key wording that signals this pattern includes:

• "maximize the area" - suggests we're looking for optimal combinations
• "container with most water" - implies we want to maximize a mathematical function (area = min(height[i], height[j]) × (j - i))
• The constraint that we can't move the x-axis (we must use indices as-is) suggests a systematic approach to explore all valid combinations

This problem fits the Two Pointers pattern because:

1. We have a clear optimization objective (maximize area)
2. The mathematical relationship between indices and heights creates a predictable pattern where moving one pointer affects the area calculation
3. There's a clear greedy strategy: we can safely eliminate certain combinations without checking all possibilities

The core insight is that for any two pointers at positions i and j, if height[i] < height[j], then moving the left pointer inward will never yield a better area than the current configuration, since:

• The width decreases
• The height is bounded by height[i] (which is smaller than height[j]) This allows us to use a greedy two-pointer approach instead of checking all O(n²) combinations.

The pattern also resembles Sliding Window in that we're maintaining a window (defined by two pointers) and systematically adjusting its boundaries to find optimal solutions, though the adjustment logic is more specific than typical sliding window problems.

3. Approach Evolution

My first instinct is to use a brute force approach where I check every possible pair of lines to calculate the area, but that's O(n²) because for each line I would need to check all other lines. Let me think about how to optimize this.

The key insight is that we want to maximize the area formed by two lines, which is calculated as min(height[i], height[j]) * (j - i). If I start with the widest possible container (leftmost and rightmost lines), I can think about when to move pointers inward.

I notice that if the left line is shorter than the right line, moving the right pointer inward won't help me find a larger area because:

1. The width will decrease
2. The height is bounded by the shorter left line
3. So we're guaranteed to get a smaller area

This suggests a two-pointer approach where I start from both ends and move the pointer pointing to the shorter line inward. This maintains an important invariant: at each step, we're considering the best possible container that could include the current shorter line.

Let me trace through this more carefully:

• Start with left=0, right=n-1
• Calculate area = min(height[left], height[right]) * (right - left)
• Move the pointer with smaller height inward
• Continue until pointers meet

This approach reduces to O(n) time complexity because we visit each element at most once, and the space complexity is O(1) since we only use a constant amount of extra space.

The key optimization here is that instead of checking all pairs, we can greedily eliminate candidates by moving the pointer with smaller height, which is mathematically sound because any container that includes a shorter line and has the same width will have a smaller area.

This is much better than O(n²) because we're making an informed decision at each step rather than checking every possibility. The two-pointer technique works because we're always maintaining the maximum possible area that could include one of our current boundary lines.

4. Data Structure Choice

For the Container With Most Water problem, I'll use a two-pointer approach with primitive int variables as the primary data structures.

Primary Data Structures Used

1. Two int pointers (left and right) - These serve as the primary data structures to track our current container boundaries
2. One int variable (maxArea) - To keep track of the maximum area found so far

Why Each Data Structure Is Needed

The two-pointer technique is optimal for this problem because:

• The pointers act as a sliding window that systematically explores all potential containers
• We only need to track the current left and right boundaries, not store intermediate states
• The maxArea variable maintains our global optimum throughout the iteration

Time and Space Impact

• Time Complexity: O(n) - We process each element at most once
• Space Complexity: O(1) - Only using a constant amount of extra space for the two pointers and maxArea variable

Helper Structure

No additional helper data structures are needed. The algorithm's efficiency comes from the mathematical property that we can greedily move the shorter of the two pointers inward, which eliminates many suboptimal containers from consideration.

The key insight is that for any container with height h[i] and h[j], if h[i] < h[j], then any container formed with h[i] and another right boundary will have smaller area than our current container. This allows us to safely discard h[i] and move the left pointer inward, reducing our search space efficiently.

This approach is superior to alternatives like storing all possible pairs (which would be O(n²) space) or using a heap-based approach, as it maintains the optimal O(1) space complexity while achieving linear time performance.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

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

Step 1: Initialize pointers

• left = 0 (points to height[0] = 1)
• right = 8 (points to height[8] = 7)
• maxArea = 0

Step 2: Calculate initial area

• Width = right - left = 8 - 0 = 8
• Height = min(height[0], height[8]) = min(1, 7) = 1
• Area = 8 × 1 = 8
• Update maxArea = max(0, 8) = 8

Step 3: Move shorter pointer inward

• Since height[0] < height[8], move left pointer right
• left = 1 (points to height[1] = 8)
• right = 8 (unchanged)

Step 4: Calculate new area

• Width = 8 - 1 = 7
• Height = min(8, 7) = 7
• Area = 7 × 7 = 49
• Update maxArea = max(8, 49) = 49

Step 5: Continue moving pointers

• height[1] > height[8], so move right left
• left = 1, right = 7
• Width = 7 - 1 = 6
• Height = min(8, 3) = 3
• Area = 6 × 3 = 18

Step 6: Continue until pointers meet

• Keep moving the shorter side inward, always calculating area and updating max
• Eventually we'll find that the maximum area is 49, achieved with indices 1 and 8

Key insight: At each step, we're guaranteed to never miss the optimal solution because moving the taller pole inward can only decrease the area, while moving the shorter pole might increase it.

Edge case handling:

• When input has only 2 elements, we calculate area immediately and return
• When pointers meet, we stop the loop
• The algorithm correctly handles duplicate heights by always moving the shorter pointer

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

6. Java Solution

public class ContainerWithMostWater {
    /**
     * Finds the maximum area formed between two vertical lines
     * using the two-pointer technique.
     * 
     * @param height Array of integers representing vertical line heights
     * @return Maximum area that can be formed
     */
    public int maxArea(int[] height) {
        // Handle edge case of null or insufficient input
        if (height == null || height.length < 2) {
            return 0;
        }
        
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        
        // Two pointers approach: move the pointer with smaller height
        while (left < right) {
            // Calculate current area
            int currentHeight = Math.min(height[left], height[right]);
            int currentWidth = right - left;
            int currentArea = currentHeight * currentWidth;
            
            // Update maximum area
            maxArea = Math.max(maxArea, currentArea);
            
            // Move the pointer with smaller height inward
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }
}

The solution implements the classic two-pointer approach for the Container With Most Water problem. It maintains two pointers at both ends of the array and moves the pointer with the smaller height inward, ensuring we never miss the optimal solution. The algorithm is optimal with O(n) time complexity and O(1) space complexity.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm uses the two-pointer technique where each pointer moves at most n-1 times total. Since we process each element at most once, the time complexity is linear.

Space Complexity: O(1)

The solution only uses a constant amount of extra space for variables left, right, maxArea, and currentArea. No additional data structures grow with input size.

Why these bounds are correct:

• Each pointer moves inward at most n-1 times total, and we perform constant-time operations at each step
• We never store more than a fixed number of variables regardless of input size
• The algorithm processes each element exactly once in the context of area calculation

Optimality:

This is optimal for this problem since we must examine each potential container configuration at least once to determine the maximum area. The two-pointer approach achieves the theoretical lower bound of O(n) time complexity for this problem, making it near-optimal. Any algorithm solving this problem must examine at least n elements to guarantee finding the maximum area, so our solution is as efficient as theoretically possible.

The linear time complexity is optimal because we cannot avoid examining each potential container configuration in the worst case, and our approach achieves this minimum necessary work.

8. Edge Cases & Pitfalls

Edge Cases

• Empty input: The problem guarantees height.length >= 2, but in interview settings, it's good to confirm that we handle arrays of size 2 correctly.
• Single element: Again, guaranteed to have at least 2 elements, but understanding the base case is important.
• All elements equal: When all heights are identical, every container has the same area, so any valid pair will return the maximum.
• Two elements only: The solution should work correctly with just two elements, where the container area is determined by the shorter height and distance between indices.

Pitfalls

• Misunderstanding area calculation: The area is calculated as min(height[i], height[j]) * (j - i). A common mistake is forgetting to take the minimum of the two heights or incorrectly calculating the width.
• Index confusion: When moving pointers, it's easy to accidentally move the wrong pointer or skip elements. Always ensure that we're moving the pointer with the smaller height to maximize potential area.
• Off-by-one errors: When handling indices, particularly in the loop condition and pointer movement logic, off-by-one errors can lead to incorrect results or infinite loops.
• Not handling duplicate heights: If multiple elements have the same height, the algorithm should still work correctly by always moving the pointer with the smaller height.
• Incorrect termination condition: The loop should continue while left < right, and not allow the pointers to cross or become equal, which would result in invalid containers.

Common Implementation Mistakes

• Incorrect pointer movement: Moving the pointer with the larger height instead of the smaller one leads to missing optimal solutions.
• Not updating pointers correctly: Failing to increment left or decrement right after comparison can cause infinite loops.
• Using wrong variable names: Confusing left, right, maxArea, or currentArea can lead to logic errors.
• Not initializing maxArea properly: Starting with zero or a negative value instead of using the first valid area can cause incorrect results.

9. Alternative Approaches

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

Brute Force Approach: The most straightforward alternative is to check all possible pairs of lines using nested loops. For each pair (i,j) where i < j, calculate the area as min(height[i], height[j]) * (j - i). This approach has O(n²) time complexity and O(1) space complexity. While simple to implement, it's inefficient for large inputs and doesn't leverage the key insight that we can optimize by moving pointers strategically.

Binary Search Approach: We could attempt to use binary search, but this is not a natural fit for this problem. The challenge with applying binary search here is that we're looking for the optimal pair of lines, not just finding a value in a sorted array. The constraint that we must consider pairs with indices i < j makes direct binary search application complex and less efficient than our two-pointer approach.

Divide and Conquer: We could theoretically divide the array into halves and recursively find the maximum area, but this approach doesn't naturally lead to a better solution. The divide and conquer method would still require checking combinations across the boundary between halves, potentially leading to O(n²) complexity in worst-case scenarios.

Dynamic Programming: While the problem involves optimization, it doesn't naturally fit a dynamic programming approach where we build solutions from subproblems. The area calculation depends on the absolute heights and positions of lines, not on optimal substructure properties that would allow us to build up solutions incrementally.

The two-pointer approach is preferred because it's the most efficient solution that takes advantage of the problem's specific structure. It's optimal in both time and space complexity, making it the ideal choice for a FAANG interview setting where efficiency matters.

The key insight that makes our chosen approach superior is that we can eliminate large portions of the search space by using the fact that moving the pointer with the smaller height inward might lead to a larger area, while moving the taller one inward can only decrease the area. This greedy property is what makes the two-pointer approach optimal.

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 current area
            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: Basic case

int[] height = {1,8,6,2,5,4,8,3,7};
// Expected: 49
// The container formed by indices 1 and 8 (heights 8 and 7)
// has width 7-1=6 and height min(8,7)=7, area = 6*7=42
// Actually the optimal is indices 1 and 8 with heights 8 and 7, area = 6*7=42
// But indices 0 and 8 give width 8-0=8, height min(1,7)=1, area = 8
// Indices 1 and 8 give width 8-1=7, height min(8,7)=7, area = 49

Example 2: Edge case - minimal array

int[] height = {1, 2};
// Expected: 1
// Width = 1, height = min(1,2) = 1, area = 1

Example 3: All same heights

int[] height = {5, 5, 5, 5};
// Expected: 10
// Any pair gives area = width * 5, maximum is with max width = 3, area = 3*5 = 15
// Actually width = 3 (indices 0 and 3), height = min(5,5) = 5, area = 15

Example 4: Monotonically increasing heights

int[] height = {1, 2, 3, 4, 5};
// Expected: 6
// Best is indices 1 and 4 (heights 2 and 5), width = 3, area = 6

Example 5: Large values with optimal at edges

int[] height = {100, 2, 3, 4, 5, 6, 7, 8, 9, 100};
// Expected: 900
// Best is indices 0 and 9 (heights 100 and 100), width = 9, area = 900

Example 6: Empty array (edge case)

int[] height = {};
// Expected: 0 (or throw exception depending on requirements)

Example 7: Single element array (edge case)

int[] height = {5};
// Expected: 0 (or throw exception depending on requirements)

Example 8: Tricky case with many local maxima

int[] height = {2, 1, 3, 1, 4, 1, 5, 1, 6, 1};
// Expected: 12
// Best is indices 2 and 8 (heights 3 and 6), width = 6, area = 18
// Actually indices 0 and 8 (heights 2 and 6), width = 8, area = 16
// Actually indices 2 and 8 (heights 3 and 6), width = 6, area = 18
// Actually indices 4 and 8 (heights 4 and 6), width = 4, area = 16
// Actually indices 0 and 6 (heights 2 and 5), width = 6, area = 12

11. Final Summary

The core idea is to use the two-pointer technique to efficiently find the maximum area by systematically eliminating suboptimal candidates. The solution works by starting with the widest possible container and greedily moving the pointer of the shorter wall inward, ensuring we never miss the optimal solution. This approach is optimal with O(n) time complexity and O(1) space complexity, making it the most efficient solution for this problem.

The key insight is that for any given container configuration, moving the taller wall inward can only decrease the area, while moving the shorter wall might increase it. This greedy property allows us to prune the search space efficiently without missing the global optimum.