24. Container With Most Water

🔗 LeetCode Problem: 11. Container With Most Water
📊 Difficulty: Medium
🏷️ Topics: Array, Two Pointers, Greedy

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 ith 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.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. 
In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints: - n == height.length - 2 <= n <= 10^5 - 0 <= height[i] <= 10^4

🎨 Visual Understanding

The Problem Visualized

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

Visual representation (vertical lines):

8 |   █           █      
7 |   █           █     █
6 |   █   █       █     █
5 |   █   █   █   █     █
4 |   █   █   █ █ █     █
3 |   █   █   █ █ █   █ █
2 |   █   █ █ █ █ █   █ █
1 | █ █   █ █ █ █ █   █ █
  +-------------------
    0 1 2 3 4 5 6 7 8

Container between index 1 and 8:
Width = 8 - 1 = 7
Height = min(8, 7) = 7
Area = 7 × 7 = 49 ✓

Understanding Water Container

Two lines form a container:
- Width: Distance between lines
- Height: Minimum of the two line heights
- Area: Width × Height

Example with indices i=1, j=6:

  8 |   █           █      
    |   █░░░░░░░░░░░█  ← Water level = min(8, 8) = 8
  7 |   █░░░░░░░░░░░█     
  6 |   █░░░░░░░░░░░█     
    |   └───────────┘
    i=1           j=6

Width = 6 - 1 = 5
Height = min(8, 8) = 8
Area = 5 × 8 = 40

Why Height is Minimum?

Water fills to the level of the shorter line:

Case 1: Different heights
  5 |   █           
  4 |   █         █  ← Water level limited by shorter line (4)
  3 |   █░░░░░░░░░█
  2 |   █░░░░░░░░░█
  1 |   █░░░░░░░░░█
    i=1         j=5

Height = min(5, 4) = 4
Water would overflow if we use height 5!

Case 2: Same heights
  4 |   █         █
  3 |   █░░░░░░░░░█  ← Both same, so min = 4
  2 |   █░░░░░░░░░█
  1 |   █░░░░░░░░░█

Height = min(4, 4) = 4

🎯 Approach 1: Brute Force (Check All Pairs)

The Most Natural Thinking 💭

Core Logic:

Check every possible pair of lines:

For each pair (i, j) where i < j:
  Calculate area = (j - i) × min(height[i], height[j])
  Track maximum area

Try all combinations!

Why This Works: - Explicitly checks all possibilities - Guaranteed to find maximum - Easy to understand

Why This is Slow: - Nested loops → O(n²) time - Too slow for large inputs (n up to 10^5) - Can we do better?

Implementation

public int maxArea(int[] height) {
    int maxArea = 0;

    // Try all pairs
    for (int i = 0; i < height.length; i++) {
        for (int j = i + 1; j < height.length; j++) {
            int width = j - i;
            int h = Math.min(height[i], height[j]);
            int area = width * h;
            maxArea = Math.max(maxArea, area);
        }
    }

    return maxArea;
}

Step-by-Step Execution: height = [1,8,6,2,5,4,8,3,7]

Check all pairs:

i=0, j=1: area = (1-0) × min(1,8) = 1 × 1 = 1
i=0, j=2: area = (2-0) × min(1,6) = 2 × 1 = 2
i=0, j=3: area = (3-0) × min(1,2) = 3 × 1 = 3
...
i=1, j=2: area = (2-1) × min(8,6) = 1 × 6 = 6
i=1, j=3: area = (3-1) × min(8,2) = 2 × 2 = 4
...
i=1, j=8: area = (8-1) × min(8,7) = 7 × 7 = 49 ✓ (max)
...

Total pairs checked: n(n-1)/2 = 36 pairs

Maximum: 49

⏰ Time: O(n²) - nested loops
💾 Space: O(1)

✅ Approach 2: Two Pointers (Optimal)

The Breakthrough Insight 💡

Core Logic:

Key observation: Use greedy approach with two pointers!

Start with widest possible container (left=0, right=n-1)
Then shrink by moving the pointer with smaller height

Why move smaller height?
- Current area limited by smaller height
- Moving smaller height might find taller line
- Moving taller height can only decrease area (width decreases, height can't increase)

Strategy:
1. Start with maximum width
2. Calculate area
3. Move pointer with smaller height inward
4. Repeat until pointers meet

Mathematical Proof:

Current state: left pointer at height h_left, right at height h_right
Assume h_left < h_right

If we move right pointer:
- Width decreases
- New height ≤ h_left (limited by smaller height)
- New area = (new width) × (≤ h_left) < current area

If we move left pointer:
- Width decreases
- New height could be > h_left (find taller line)
- Possibility of larger area!

Therefore: Always move the pointer with smaller height

Why This is Better: - O(n) time - single pass - Each element visited at most once - No nested loops needed - Optimal solution!

Implementation

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 h = Math.min(height[left], height[right]);
        int area = width * h;
        maxArea = Math.max(maxArea, area);

        // Move pointer with smaller height
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxArea;
}

Step-by-Step Execution: height = [1,8,6,2,5,4,8,3,7]

Initial State:
═══════════════════════════════════════════════════════════════════
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
          ↑                       ↑
         left                   right
maxArea = 0


Iteration 1:
═══════════════════════════════════════════════════════════════════
left=0, right=8
width = 8 - 0 = 8
h = min(height[0], height[8]) = min(1, 7) = 1
area = 8 × 1 = 8
maxArea = max(0, 8) = 8

height[0]=1 < height[8]=7 → move left
left++ → left=1

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
             ↑                    ↑
            left                right


Iteration 2:
═══════════════════════════════════════════════════════════════════
left=1, right=8
width = 8 - 1 = 7
h = min(height[1], height[8]) = min(8, 7) = 7
area = 7 × 7 = 49
maxArea = max(8, 49) = 49 ✓

height[1]=8 > height[8]=7 → move right
right-- → right=7

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
             ↑                 ↑
            left             right


Iteration 3:
═══════════════════════════════════════════════════════════════════
left=1, right=7
width = 7 - 1 = 6
h = min(height[1], height[7]) = min(8, 3) = 3
area = 6 × 3 = 18
maxArea = max(49, 18) = 49

height[1]=8 > height[7]=3 → move right
right-- → right=6

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
             ↑              ↑
            left          right


Iteration 4:
═══════════════════════════════════════════════════════════════════
left=1, right=6
width = 6 - 1 = 5
h = min(height[1], height[6]) = min(8, 8) = 8
area = 5 × 8 = 40
maxArea = max(49, 40) = 49

height[1]=8 == height[6]=8 → move right (or left, doesn't matter)
right-- → right=5

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
             ↑           ↑
            left       right


Iteration 5:
═══════════════════════════════════════════════════════════════════
left=1, right=5
width = 5 - 1 = 4
h = min(height[1], height[5]) = min(8, 4) = 4
area = 4 × 4 = 16
maxArea = max(49, 16) = 49

height[1]=8 > height[5]=4 → move right
right-- → right=4

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
             ↑        ↑
            left    right


Iteration 6:
═══════════════════════════════════════════════════════════════════
left=1, right=4
width = 4 - 1 = 3
h = min(height[1], height[4]) = min(8, 5) = 5
area = 3 × 5 = 15
maxArea = max(49, 15) = 49

height[1]=8 > height[4]=5 → move right
right-- → right=3

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
             ↑     ↑
            left right


Iteration 7:
═══════════════════════════════════════════════════════════════════
left=1, right=3
width = 3 - 1 = 2
h = min(height[1], height[3]) = min(8, 2) = 2
area = 2 × 2 = 4
maxArea = max(49, 4) = 49

height[1]=8 > height[3]=2 → move right
right-- → right=2

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
             ↑  ↑
            left
               right


Iteration 8:
═══════════════════════════════════════════════════════════════════
left=1, right=2
width = 2 - 1 = 1
h = min(height[1], height[2]) = min(8, 6) = 6
area = 1 × 6 = 6
maxArea = max(49, 6) = 49

height[1]=8 > height[2]=6 → move right
right-- → right=1

left == right → Stop

═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 49
═══════════════════════════════════════════════════════════════════

Another Example: height = [1,1]

Initial: left=0, right=1

Iteration 1:
width = 1 - 0 = 1
h = min(1, 1) = 1
area = 1 × 1 = 1
maxArea = 1

height[0]=1 == height[1]=1 → move either
right-- → right=0

left >= right → Stop

Result: 1

Example: height = [4,3,2,1,4]

Initial: left=0, right=4, maxArea=0

Iteration 1: width=4, h=min(4,4)=4, area=16, maxArea=16
  4==4 → move right, right=3

Iteration 2: width=3, h=min(4,1)=1, area=3, maxArea=16
  4>1 → move right, right=2

Iteration 3: width=2, h=min(4,2)=2, area=4, maxArea=16
  4>2 → move right, right=1

Iteration 4: width=1, h=min(4,3)=3, area=3, maxArea=16
  4>3 → move right, right=0

left >= right → Stop

Result: 16

⏰ Time: O(n) - single pass with two pointers
💾 Space: O(1) - only two pointers

🔍 Edge Cases

Case 1: Minimum size (two elements)
Input: height = [1,1]
Output: 1
Strategy: Only one possible container

Case 2: Ascending heights
Input: height = [1,2,3,4,5]
Output: 6
Explanation: Container between 1 and 5: width=4, h=min(1,5)=1, area=4
            OR between 2 and 5: width=3, h=min(2,5)=2, area=6 ✓

Case 3: Descending heights
Input: height = [5,4,3,2,1]
Output: 6
Explanation: Container between 0 and 3: width=3, h=min(5,2)=2, area=6

Case 4: All same height
Input: height = [3,3,3,3]
Output: 9
Explanation: Maximum width with same height: 3×3=9

Case 5: Two tall ends
Input: height = [10,1,1,1,10]
Output: 40
Explanation: Container between 0 and 4: width=4, h=min(10,10)=10, area=40

Case 6: Peak in middle
Input: height = [1,8,6,2,5,4,8,3,1]
Output: 49

Case 7: Zero heights
Input: height = [0,2,0]
Output: 0
Explanation: Containers with 0 have area 0

Case 8: Large width small heights
Input: height = [1,1,1,1,1,1,1,1,1,1]
Output: 9
Explanation: width=9, h=1, area=9

Common Mistakes

Mistake 1: Moving the wrong pointer
❌ Wrong: Always move left or always move right
✓ Right: Move pointer with smaller height

Mistake 2: Not using Math.min for height
❌ Wrong: h = height[left] or h = height[right]
✓ Right: h = Math.min(height[left], height[right])

Mistake 3: Wrong width calculation
❌ Wrong: width = right + left
✓ Right: width = right - left

Mistake 4: Moving both pointers
❌ Wrong: left++; right--;
✓ Right: Move only one (the one with smaller height)

Mistake 5: Wrong loop condition
❌ Wrong: while (left <= right)
✓ Right: while (left < right)
Reason: Need two different lines

Mistake 6: Not checking for better area
❌ Wrong: Only calculate area at certain positions
✓ Right: Check area at every iteration

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(1)
  Use: Too slow for large inputs

Approach 2: Two Pointers (OPTIMAL)
  Time: O(n)
  Space: O(1)
  Use: Best solution, optimal

🔑 The Core Insight

Problem: Find maximum water container area

Formula: Area = width × height
- Width: Distance between two lines
- Height: Minimum of two line heights

Key observation:
→ Start with maximum width (left=0, right=n-1)
→ Area limited by shorter line
→ Moving taller line can't improve area (width decreases, height can't increase)
→ Moving shorter line might find taller line

Greedy strategy: Always move the shorter line
→ This maximizes chance of finding larger area
→ Guaranteed to find optimal solution

🎯 Pattern Recognition

Problem Type: Optimization with Two Pointers
Core Pattern: Two Pointers from Opposite Ends

When to Apply:
✓ Need to maximize/minimize some value
✓ Formula involves distance between elements
✓ Can make greedy decision about which pointer to move
✓ Array elements represent barriers/heights

Key Techniques:
→ Start from opposite ends
→ Greedy choice: move pointer that might improve result
→ Track maximum/minimum as we go
→ Single pass O(n) optimization

Related Problems:
- Trapping Rain Water (LC 42)
- 3Sum (LC 15)
- Two Sum II (LC 167)
- Sort Colors (LC 75)

🧠 Interview Strategy

Step 1: "Need to maximize area = width × height"
Step 2: "Brute force checks all pairs - O(n²)"
Step 3: "Key insight: start with max width, shrink wisely"
Step 4: "Move pointer with smaller height (greedy)"
Step 5: "Single pass O(n) with two pointers"

📝 Quick Revision Notes

🎯 Core Concept:

Use two pointers from opposite ends. Calculate area, then move pointer with smaller height inward. Track maximum area. Greedy approach guarantees optimal solution.

⚡ Quick Implementation:

For more understanding...

public int maxArea(int[] a) {
    int len = a.length;
    int res = Integer.MIN_VALUE;
    // // Approach 1 - brute force - if we understand this, then only we will 
    // // understand the actual problem. Problem statement is little confusing.        
    // for(int i = 0; i < len ; i++) {
    //     for(int j = i + 1; j < len ; j++) {
    //         int width = j - i;
    //         int height = Math.min(a[i], a[j]);
    //         res = Math.max(res, width * height);
    //     }
    // }

    // Approach 2 - using 2 pointers (from opposite directions) in Greedy 
    int i = 0;
    int j = len - 1;
    while (i <= j) {
        int width = j - i;
        int height = Math.min(a[i], a[j]);
        res = Math.max(res, width * height);

        // Think GREEDY
        // if left side height is less than right side height, moving
        // left side to get slightly more height than right side will increase
        // the overall area of the container. Hence, need to move left.
        if(a[i] < a[j]) {
            i++;
        } else {
            j--;
        }
    }

    return res;
}

🔑 Key Insights:

Area formula: width × min(height[left], height[right])
Start wide: left=0, right=n-1 (maximum width)
Greedy move: always move smaller height pointer
Why greedy works: moving taller line can't improve area
Single pass: O(n) time complexity
Loop condition: left < right (need two different lines)
Track maximum: update maxArea at each step
Space: O(1) - only two pointers

🎪 Memory Aid:

"Start wide, move short, track max!"
Think: "Shorter line limits water, so move it"

Trapping Rain Water (LC 42)
3Sum (LC 15)
Two Sum II - Input Array Is Sorted (LC 167)
Sort Colors (LC 75)

Happy practicing! 🎯

24. Container With Most Water

Problem Statement

🎨 Visual Understanding

The Problem Visualized

Understanding Water Container

Why Height is Minimum?

🎯 Approach 1: Brute Force (Check All Pairs)

The Most Natural Thinking 💭

Implementation

Step-by-Step Execution: height = [1,8,6,2,5,4,8,3,7]

✅ Approach 2: Two Pointers (Optimal)

The Breakthrough Insight 💡

Implementation

Step-by-Step Execution: height = [1,8,6,2,5,4,8,3,7]

Another Example: height = [1,1]

Example: height = [4,3,2,1,4]

🔍 Edge Cases

Common Mistakes

🎯 Key Takeaways

⚡ Algorithm Comparison

🔑 The Core Insight

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

Related Patterns