LeetCode 11 Solution & Blind 75 - problem 10 : Container With Most Water

Problem Statement (LeetCode 11 - Container With Most Water)

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are at (i, 0) and (i, height[i]).

Find two lines that, together with the x-axis, form a container that holds the most water.
Return the maximum amount of water a container can store.

Constraints

• 2 <= height.length <= 10^5
• 0 <= height[i] <= 10^4

---

Examples

Example 1

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The container is formed between indices 1 and 8, giving area = 7 * min(8,7) = 49.

Example 2

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

---

Optimal Approach: Two-Pointer Technique

Intuition

• Use two pointers, one at the leftmost (l = 0) and one at the rightmost (r = n - 1).
• Calculate area using the formula: $$\text{area} = (\text{right index} - \text{left index}) \times \min(\text{height[left]}, \text{height[right]})$$
• Move the pointer with the smaller height since the area is limited by the shorter height.

---

LeetCode-Compatible C++ Code

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxWater = 0;
        int left = 0, right = height.size() - 1;
        
        while (left < right) {
            int h = min(height[left], height[right]);
            maxWater = max(maxWater, h * (right - left));
            
            // Move the pointer with the smaller height
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxWater;
    }
};

---

Step-by-Step Explanation

1. Initialize Two Pointers:

   • left = 0, right = n-1.
   • maxWater = 0 to track the maximum container size.

2. Iterate Until Pointers Meet:

   • Compute the water storage: $$\text{current area} = (right - left) \times \min(height[left], height[right])$$
   • Update maxWater if the current area is greater.

3. Move the Pointer with the Smaller Height:

   • If height[left] < height[right], move left++ (hoping for a taller height).
   • Otherwise, move right--.

4. Return the Maximum Area found.

---

Dry Run with Example

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

Step 1: left = 0, right = 8, area = 8 * min(1,7) = 8
Step 2: left = 1, right = 8, area = 7 * min(8,7) = 49 (maxWater updated)
Step 3: left = 1, right = 7, area = 6 * min(8,3) = 18
Step 4: left = 1, right = 6, area = 5 * min(8,8) = 40
...
Final maxWater = 49

✅ Output: 49

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Nested Loops)	O(n²)	O(1)	Too slow for large n (up to 10^5)
Sorting (Invalid)	O(n log n)	O(n)	Sorting does not help in maximizing the area
Two-Pointer (Best)	O(n)	O(1)	Efficient and optimal

---

Why Two-Pointer is the Best

1. Optimized for Large Inputs (n ≤ 10^5) → O(n) is feasible.
2. Avoids unnecessary comparisons (Unlike Brute Force).
3. Space Efficient (O(1)) → Uses only two extra variables.

---

Conclusion

✅ Best approach: Two-Pointer Technique
✅ Time Complexity: O(n)
✅ Space Complexity: O(1)
✅ Avoids Brute Force inefficiencies

Recommended Problems for Practice

1. Trapping Rain Water 🌊
2. Largest Rectangle in Histogram 📊
3. Sliding Window Maximum 🪟

🚀 Master the Two-Pointer Technique for Optimal Solutions!