Container With Most Water

height[i] is the height of a vertical line standing at position i. Choose two of the lines so that, with the x-axis as the floor, the container they form holds as much water as possible.

Goal: Maximize Area = width * min(height[left], height[right]).

The container is formed by two vertical lines, and its water level is limited by the shorter one. The figure below outlines the water between the two pointers at that level.

The naive solution is to simply check every pair of lines and calculate the area.

• Check line 0 with line 1, then line 0 with line 2...
• Then line 1 with line 2, line 1 with line 3...

Why it fails: This requires nested loops, resulting in O(n^2) time complexity. For a large input, this will time out.

Start Wide, Then Eliminate.

1. Start Max Width: The widest possible container is bounded by the first and last line. Let's start there.
2. The Decision: We want to find a higher line to potentially get more area. But we can only move one pointer at a time.
   • If height[left] < height[right], the left line is the bottleneck. Moving the right pointer in would only decrease width, and height is still limited by left. We must move left to hope for a taller line.
   • Similarly, if right is shorter, we must discard it and move right inward.

1. Start with pointers at both ends: left = 0, right = n-1.
2. Calculate the current area: min(height[left], height[right]) * (right - left).
3. Update the maximum area found so far.
4. Decision: Compare the heights of left and right. Move the pointer pointing to the shorter line inwards.
   • If height[left] < height[right], increment left.
   • Else, decrement right.
5. Repeat until the pointers meet.

Compare Every pair with Two pointers on the same heights: the pointer scan moves the shorter line inward each time and still finds the best area, computing far fewer areas (Checks).