Container With Most Water

Determining the maximum water a container can hold between vertical lines is foundational in graphics rendering, fluid simulations, and two-pointer optimizations. The “Container With Most Water” problem challenges you to squeeze the best area in O(n) time.

Problem Statement

Given an array height of non-negative integers, where each element represents the height of a vertical line at that index, find two lines that, together with the x-axis, form a container that holds the most water. Return the maximum area.

Example:
height = [1,8,6,2,5,4,8,3,7]
Max area is formed between lines at indices 1 (height=8) and 8 (height=7):
width = 8 − 1 = 7, minHeight = 7 ⇒ area = 7×7 = 49

1. Clarify Requirements Before Jumping Into Code

I need to confirm:

• We treat widths as index distances.

• Water capacity is width × min(height[left], height[right]).

• We must pick two distinct indices.

• Array length ≥ 2.

• Optimal time is O(n), space O(1).

2. Identify the Category of the Question

At first glance this brings to mind the two-pointer pattern, as well as a greedy optimization approach on an array. Some ideas that come to mind:

• Brute-force pair scanning.

• Shrinking window with left/right pointers based on boundary heights.

• Using max area seen so far.

3. Consider a Brute-Force Approach to Understand the Problem

For a brute-force solution, we simply check every pair (i,j) with i < j:

maxArea = 0
for i in 0..n-2:
  for j in i+1..n-1:
    area = (j-i) × min(height[i], height[j])
    update maxArea
return maxArea

This gives us a runtime of O(n²), which is far too slow.

4. Brainstorm More Solutions

Let's think about how we can improve on our brute-force solution. We get O(n²) time because we are reprocessing the entire array for every element. What's the best we can do in terms of runtime? Well we know we'll have to check every element at least once, so that means the best we can hope for is O(n) time. So, can we come up with a solution that only requires one or two passes through the array?

Ultimately we're looking for a pair of elements, so what if we used a two-pointer approach? We could start with the biggest possible window - left = 0, right = n-1 and calculate our area. We'll store this in a maxArea variable.

Now how do we choose which pointer to move? Well, we know we want to maximize our area. If we only move a pointer by 1 on every iteration, the only way to increase our area is to increase the height of the smaller pointer. So, on every iteration, let's just take the pointer with the smaller height and move it inwards, hoping to find a larger height. We'll keep doing this until our pointers meet, updating our maxArea any time we encounter a pair with a larger area. This gives us O(n) time and O(1) space - as good as it gets.

5. Discuss Trade-Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Brute-force pair scan	O(n²)	O(1)	Trivial	Too slow for large n
Two-pointer shrinking	O(n)	O(1)	Optimal, simple	Requires the insight to move shorter pointer

6. Write Pseudocode to Structure Your Thoughts

function maxArea(height):
  left = 0
  right = length(height) - 1
  maxArea = 0
  while left < right:
    width = right - left
    h = min(height[left], height[right])
    maxArea = max(maxArea, width * h)
    if height[left] < height[right]:
      left += 1
    else:
      right -= 1
  return maxArea

7. Consider Edge Cases

• Only two lines → single area.

• All heights equal → area grows as width shrinks, maximum at ends.

• Monotonically increasing heights → pointer moves inward from left only.

• Monotonically decreasing → pointer moves inward from right only.

8. Write Full Code Syntax

public class Solution {
    public int maxArea(int[] height) {
        int left = 0, 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);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    System.out.println(sol.maxArea(new int[]{1,8,6,2,5,4,8,3,7}) == 49);
    System.out.println(sol.maxArea(new int[]{1,1}) == 1);
    System.out.println(sol.maxArea(new int[]{4,3,2,1,4}) == 16);
    System.out.println(sol.maxArea(new int[]{1,2,1}) == 2);
    System.out.println(sol.maxArea(new int[]{2,3,10,5,7,8,9}) == 36);
}

10. Key Lessons to Remember for Future Questions

• Two-pointer shrinking window solves many “maximize function over pairs” in linear time.

• Recognize that width decreases by one each step; only height improvements can pay off.

• Taking a moment to consider the best possible runtime can be a good starting point when you're brainstorming solutions.

Good Luck and Happy Coding!