Container With Most Water

Practice Here

brute Force#

The simplest approach is to enumerate every possible pair of vertical lines and compute the water each pair can hold. For a pair (i, j), the area is min(height[i], height[j]) * (j - i) — the shorter bar is the bottleneck, and the width is the gap between them. We track the running maximum over all O(n²) pairs, which is correct but slow.

• Try every pair (i, j), compute the area, and update the maximum.

int maxArea(vector<int>& height) {
    int n = height.size();
    int maxArea = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int h = min(height[i], height[j]);
            int w = j - i;
            maxArea = max(maxArea, h * w);
        }
    }
    return maxArea;
}

Time Complexity: O(n²)

Space Complexity: O(1)

Optimal Solution: Two pointer#

Instead of checking every pair, we start with the widest possible container (one pointer at each end) and greedily shrink it. The key insight is that the area is always limited by the shorter bar, so moving the taller bar's pointer inward can only make things worse — the width shrinks and the height can only stay the same or decrease. Moving the shorter bar's pointer inward is the only move that can improve the area, because a taller bar might compensate for the reduced width. This greedy choice lets us visit only O(n) pairs instead of O(n²).

• Start with two pointers: left = 0, right = n - 1
• Compute area
• Move the pointer with smaller height inward (hoping for a taller line)
• Repeat until left < right

class Solution {
public:
    int maxArea(vector<int>& height) {
        
        int maxArea = INT_MIN;
        int n = height.size();
        
        int startIdx = 0, endIdx = n-1;
        while(startIdx<=endIdx)
        {
            int currHeight = min(height[startIdx], height[endIdx]);
            int currWidth = endIdx - startIdx;

            maxArea = max(currHeight * currWidth, maxArea);
            if(height[startIdx] < height[endIdx])
                startIdx++;
            else
                endIdx--;
        }
        return maxArea;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)