11. Container With Most Water

Time: O(n)

Space: O(1)

Intuition

Place two pointers at opposite ends and ask: which pointer should move? The area is limited by the shorter side. Moving the taller side inward can only keep or reduce the height limit while reducing width - guaranteed to be worse. Moving the shorter side inward may find a taller line that compensates for the reduced width. So always advance the shorter pointer.

Algorithm

1Initialise left = 0, right = n-1, maxArea = 0.
2While left < right: compute area = min(height[left], height[right]) * (right - left).
3Update maxArea = max(maxArea, area).
4Advance the pointer pointing to the shorter line: if height[left] < height[right] -> left++; else -> right--.
5Return maxArea.

Example Walkthrough

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

1.left=0 (h=1), right=8 (h=7): area = 1*8 = 8. height[left]<height[right] -> left++.
2.left=1 (h=8), right=8 (h=7): area = 7*7 = 49. height[right]<height[left] -> right--.
3.left=1 (h=8), right=7 (h=3): area = 3*6 = 18. right--.
4.Continue until left=1, right=6 (h=8): area = 8*5 = 40.
5.Max found so far is 49 - no further pair beats it.

Output: 49

Common Pitfalls

•Do NOT move the pointer with the greater height - that is always suboptimal.
•The algorithm works because if a better container exists, the two-pointer sweep is guaranteed to visit it.

11.cs

// Approach: Two pointers starting at both ends of the array.
// The water volume between two lines equals the shorter height multiplied by the distance between them.
// Start with left=0 and right=n-1 to maximise the width, then shrink inward.
// Always advance the pointer at the shorter side — moving the taller side can only decrease area.
// Track the maximum area seen across all valid pairs.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaxArea(int[] height)
    {
        int n = height.Length;
        int l = 0;
        int r = n - 1;
        int maxWater = 0;
        while (l <= r)
        {
            if (height[l] <= height[r])
            {
                int water = height[l] * (r - l);
                maxWater = Math.Max(water, maxWater);
                l++;
            }
            else
            {
                int water = height[r] * (r - l);
                maxWater = Math.Max(water, maxWater);
                r--;
            }
        }

        return maxWater;
    }
}

Was this solution helpful?