How to Solve: Container With Most Water

How to Solve: Container With Most Water

Complete Guide for FAANG-Level Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—mastering it proves you can optimize brute-force solutions into O(n) time with O(1) space, a skill that separates strong candidates from the rest."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Two-pointer technique (how to move pointers based on conditions). 2. Greedy algorithms (making locally optimal choices to reach a global optimum). 3. Time/space complexity analysis (Big-O notation, trade-offs).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Repeatable mental checklist for every "Container With Most Water" problem:

1. Understand the problem:
2. Given an array height of n non-negative integers, where height[i] represents the height of a vertical line at index i.
3. Find two lines that, together with the x-axis, form a container that holds the most water.

4. Return the maximum area (width × height).

5. Brute-force intuition (for understanding):

6. For every pair (i, j), compute area = min(height[i], height[j]) (j - i).
7. Track the maximum area.

8. Time: O(n²), Space: O(1) → Too slow for large n.

9. Optimize with two pointers:

10. Initialize left = 0, right = n - 1.
11. While left < right:
    • Compute current_area = min(height[left], height[right]) (right - left).
    • Update max_area if current_area is larger.
    • Move the pointer pointing to the smaller height inward (greedy choice).

12. Why? Moving the smaller height might lead to a larger area (since width decreases, height must increase to compensate).

13. Edge cases:

14. n < 2 → Return 0 (no container possible).
15. All heights equal → Any pair gives the same area.

16. Duplicates → Pointer movement handles ties naturally.

17. Time/space complexity:

18. Time: O(n) (each element visited once).
19. Space: O(1) (no extra data structures).

? WORKED EXAMPLES

Example 1 – Basic

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] Expected Output: 49 (from lines at indices 1 and 8).

Step-by-step: 1. Initialize left = 0, right = 8, max_area = 0. 2. Iteration 1:
- height[left] = 1, height[right] = 7.
- current_area = min(1, 7) (8 - 0) = 8.
- max_area = max(0, 8) = 8.
- Move left (since 1 < 7). 3. Iteration 2:
- left = 1, right = 8.
- current_area = min(8, 7) (8 - 1) = 49.
- max_area = 49.
- Move right (since 7 < 8). 4. Iteration 3:
- left = 1, right = 7.
- current_area = min(8, 3) (7 - 1) = 18.
- max_area remains 49.
- Move right (since 3 < 8). 5. ... (continue until left >= right).

Code (Python):

def maxArea(height):

    left, right = 0, len(height) - 1

    max_area = 0

    while left < right:

        current_area = min(height[left], height[right])  (right - left)

        max_area = max(max_area, current_area)

        if height[left] < height[right]:

            left += 1

        else:

            right -= 1

    return max_area

Why this works: - The two-pointer approach eliminates unnecessary pairs by always moving the smaller height, ensuring we explore potentially larger areas efficiently.

Example 2 – Medium (Duplicates)

Input: height = [1, 1, 1, 1, 10, 1, 1, 10, 1, 1, 1] Expected Output: 20 (from lines at indices 4 and 7).

Key Insight: - Duplicates don’t break the algorithm. The pointer movement handles ties by moving either pointer (both choices are valid).

Code: - Same as above. The algorithm naturally skips duplicates by moving pointers inward.

Example 3 – Hard/Follow-up (3D Container)

Problem: Given a 2D grid where grid[i][j] represents the height of a pillar at (i, j), find the maximum volume of water that can be trapped between any two pillars.

Approach: 1. Brute-force: O(n⁴) → Check all pairs of pillars and compute volume. 2. Optimized:
- For each row, compute the "effective height" (minimum of the two pillars in the row).
- Use the two-pointer technique on the effective heights to find the maximum area.
- Time: O(n²) (for each row, O(n) two-pointer pass).

Code (Python):

def maxArea3D(grid):

    max_volume = 0

    rows = len(grid)

    for i in range(rows):

        for j in range(i + 1, rows):

            # Compute effective heights for columns

            effective_heights = [min(grid[i][k], grid[j][k]) for k in range(len(grid[0]))]

            # Two-pointer on effective_heights

            left, right = 0, len(effective_heights) - 1

            current_max = 0

            while left < right:

                current_area = min(effective_heights[left], effective_heights[right])  (right - left)

                current_max = max(current_max, current_area)

                if effective_heights[left] < effective_heights[right]:

                    left += 1

                else:

                    right -= 1

            max_volume = max(max_volume, current_max  (j - i))

    return max_volume

Why this works: - The 3D problem reduces to multiple 1D "Container With Most Water" problems (one per pair of rows), leveraging the same two-pointer optimization.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Here’s your 60-second recap before the interview: 1. Problem: Find two lines in an array that form the largest container (area = width × height). 2. Brute-force is O(n²)—too slow. Optimize with two pointers. 3. Initialize left = 0, right = n - 1. 4. While left < right:
- Compute current_area = min(height[left], height[right]) (right - left).
- Update max_area.
- Move the pointer with the smaller height (greedy choice). 5. Edge cases: n < 2 → return 0. Duplicates? No problem. 6. Time: O(n), Space: O(1)—optimal. 7. Follow-ups: 3D version? Reduce to multiple 1D problems. You’ve got this. Walk in, write the code, and explain the greedy choice. Good luck!

? Final Notes

• Practice: Solve variations (e.g., "Trapping Rain Water") to reinforce the two-pointer pattern.
• Whiteboard: Sketch the array and pointer movements to visualize the algorithm.
• Confidence: This problem is a confidence booster—if you nail it, you’re ready for harder optimizations.