Container with most water

Two walls and the water between them: close in from both ends, always moving the shorter wall.

The idea

The water held between two walls is capped by the shorter one, times the distance between them. Starting at the widest span and moving the shorter wall inward is safe: moving the taller wall can only shrink the width without ever raising the cap.

Code

public static int MaxArea(int[] h) {
    int l = 0, r = h.Length - 1, best = 0;
    while (l < r) {
        int area = Math.Min(h[l], h[r]) * (r - l);
        best = Math.Max(best, area);
        if (h[l] < h[r]) l++;
        else r--;
    }
    return best;
}

Tips

• Moving the taller pointer can never help: the cap stays the same or drops, and the width only shrinks.
• This is the same closing-in shape as pair sum, just maximising a different score.

In the .NET library

Checking every pair of walls is O(n²); this single inward pass is the O(n) answer interviewers expect.