Container With Most Water

LeetCode 11: Container With Most Water Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a two-pointer approach starting from both ends of the array, iteratively moving the pointer pointing to the shorter line inward to maximize the potential area.

The "Container With Most Water" problem asks us to find two vertical lines within an array of line heights that, together with the x-axis, form a container capable of holding the maximum amount of water. The amount of water is determined by the area of the rectangle formed by the two lines. The height of this rectangle is limited by the shorter of the two lines, and the width is the distance between the indices of the lines.

This is a classic optimization problem found in LeetCode 11, often used in technical interviews to test understanding of greedy strategies and array manipulation.

Brute Force Approach for Container With Most Water

The most intuitive way to solve this problem is to calculate the area for every possible pair of lines and keep track of the maximum area found.

1. Initialize a variable maxArea to 0.
2. Use a nested loop structure. The outer loop iterates i from 0 to n-1.
3. The inner loop iterates j from i+1 to n-1.
4. For each pair (i, j), calculate the width as (j - i).
5. Calculate the height as min(height[i], height[j]).
6. Update maxArea if the current area is larger.

1# Pseudo-code for Brute Force
2max_area = 0
3for i from 0 to n-1:
4    for j from i+1 to n-1:
5        current_area = min(height[i], height[j]) * (j - i)
6        max_area = max(max_area, current_area)
7return max_area

Time Complexity: $O(n^2)$. We check $\frac{n(n-1)}{2}$ pairs. Why it fails: The constraints state that $n$ can be up to $10^5$. An $O(n^2)$ solution results in approximately $10^{10}$ operations, which far exceeds the standard time limit (usually around $10^8$ operations per second). This leads to a Time Limit Exceeded (TLE) error on large test cases.

Algorithm Strategy: Two Pointer Patterns

We utilize the Two Pointer - Converging strategy to reduce the time complexity from quadratic to linear.

1. Initialization: Create two pointers, left pointing to the beginning of the array (index 0) and right pointing to the end (index n-1). Initialize a variable to track the maximum area found so far.
2. Constraint Logic: The constraint is the relative height of the lines. The pointer pointing to the smaller height is always the limiting factor.
3. Movement Rule:
   • Calculate the current area defined by left and right.
   • Update the maximum area.
   • If height[left] < height[right], increment the left pointer. This eliminates index left from future consideration.
   • Otherwise, decrement the right pointer. This eliminates index right from future consideration.
4. Termination: The process continues until the left and right pointers meet.

Execution Flow

Let's trace the algorithm with the input height = [1, 8, 6, 2, 5, 4, 8, 3, 7].

1. Start: left = 0 (val 1), right = 8 (val 7).

   • Width = 8. Height = min(1, 7) = 1. Area = 8.
   • height[left] < height[right]. Move left to 1.

2. Step 2: left = 1 (val 8), right = 8 (val 7).

   • Width = 7. Height = min(8, 7) = 7. Area = 49. (Max updated).
   • height[right] < height[left]. Move right to 7.

3. Step 3: left = 1 (val 8), right = 7 (val 3).

   • Width = 6. Height = min(8, 3) = 3. Area = 18.
   • height[right] < height[left]. Move right to 6.

4. Step 4: left = 1 (val 8), right = 6 (val 8).

   • Width = 5. Height = min(8, 8) = 8. Area = 40.
   • Heights equal (arbitrarily move right). Move right to 5.

5. Step 5: left = 1 (val 8), right = 5 (val 4).

   • Width = 4. Height = min(8, 4) = 4. Area = 16.
   • height[right] < height[left]. Move right to 4.

6. Step 6: left = 1 (val 8), right = 4 (val 5).

   • Width = 3. Height = min(8, 5) = 5. Area = 15.
   • height[right] < height[left]. Move right to 3.

7. Step 7: left = 1 (val 8), right = 3 (val 2).

   • Width = 2. Height = min(8, 2) = 2. Area = 4.
   • height[right] < height[left]. Move right to 2.

8. Step 8: left = 1 (val 8), right = 2 (val 6).

   • Width = 1. Height = min(8, 6) = 6. Area = 6.
   • height[right] < height[left]. Move right to 1.

9. End: left meets right. Return Max Area: 49.

Proof of Correctness

To prove this greedy strategy works, consider the state where we have pointers at left and right, and assume height[left] < height[right].

The algorithm decides to move left to left + 1. This effectively discards all pairs (left, k) where left < k < right. Is it possible that one of these discarded pairs has a larger area than the current (left, right)?

• The width of any pair (left, k) is k - left. Since k < right, the width k - left is strictly less than right - left.
• The height of the pair (left, k) is min(height[left], height[k]). This value can be at most height[left].
• Therefore, the area of (left, k) is at most height[left] * (k - left), which is strictly less than height[left] * (right - left).

Thus, the pair (left, right) provides the maximum possible area involving the index left. We can safely discard left and narrow our search space without missing the global maximum.

Pattern Reuse Notes

The Two Pointers - Converging pattern is a fundamental technique for optimizing array problems, particularly when searching for pairs or triplets that satisfy a condition. This pattern is directly applicable to:

• LeetCode 15: 3Sum - Uses a fixed pointer and two converging pointers to find triplets summing to zero.
• LeetCode 16: 3Sum Closest - Similar to 3Sum, but tracks the minimum difference to a target.
• LeetCode 18: 4Sum - Extends the pattern to four numbers, reducing complexity from $O(n^4)$ to $O(n^3)$.
• LeetCode 167: Two Sum II - Input Array Is Sorted - The classic base case for this pattern where pointers move based on the sum relative to a target.

Reference Implementation

C++ Solution for LeetCode 11

1class Solution {
2public:
3    int maxArea(vector<int>& height) {
4        int left = 0;
5        int right = height.size() - 1;
6        int max_area = 0;
7
8        while (left < right) {
9            // Calculate current area
10            int width = right - left;
11            int current_height = min(height[left], height[right]);
12            max_area = max(max_area, width * current_height);
13
14            // Move the pointer corresponding to the shorter line
15            if (height[left] < height[right]) {
16                left++;
17            } else {
18                right--;
19            }
20        }
21        return max_area;
22    }
23};

Java Solution for LeetCode 11

1class Solution {
2    public int maxArea(int[] height) {
3        int left = 0;
4        int right = height.length - 1;
5        int maxArea = 0;
6
7        while (left < right) {
8            // Calculate current area
9            int width = right - left;
10            int currentHeight = Math.min(height[left], height[right]);
11            maxArea = Math.max(maxArea, width * currentHeight);
12
13            // Move the pointer corresponding to the shorter line
14            if (height[left] < height[right]) {
15                left++;
16            } else {
17                right--;
18            }
19        }
20        return maxArea;
21    }
22}

Python Solution for LeetCode 11

1class Solution:
2    def maxArea(self, height: List[int]) -> int:
3        left = 0
4        right = len(height) - 1
5        max_area = 0
6
7        while left < right:
8            # Calculate current area
9            width = right - left
10            current_height = min(height[left], height[right])
11            max_area = max(max_area, width * current_height)
12
13            # Move the pointer corresponding to the shorter line
14            if height[left] < height[right]:
15                left += 1
16            else:
17                right -= 1
18        
19        return max_area