Why move the pointer at the shorter line?

The shorter line caps the water level. Moving the taller line inward only narrows the container while the height stays capped, so every such container is smaller; only moving the shorter line can find a taller boundary.

Does the greedy pointer scan ever miss the best container?

No. Each move discards only containers that cannot beat one already measured, so the maximum area seen during the scan is the true maximum.

What is the time complexity of Container With Most Water?

O(n) time and O(1) extra space with two pointers, against O(n²) for computing the area of every pair of lines.

Container With Most Water

Pick the two vertical lines that, with the x-axis as the floor, hold the most water between them.

MediumSolve on LeetCode

Examples

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

Output:49

Explain:

The best pair is the line of height 8 at index 1 and the line of height 7 at index 8: they stand 7 apart and the shorter is 7 tall, so they hold 7 × 7 = 49.

The Problem

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]).

Visualizing the Problem

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.

Attempt 1: Brute Force

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.

The Intuition: Process of Elimination

Start Wide, Then Eliminate.

Start Max Width: The widest possible container is bounded by the first and last line. Let's start there.
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.

Algorithm Strategy

Start with pointers at both ends: left = 0, right = n-1.
Calculate the current area: min(height[left], height[right]) * (right - left).
Update the maximum area found so far.
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.
Repeat until the pointers meet.

Interactive Walkthrough

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).

Dry Run Table

Step	Left (val)	Right (val)	Width	Height	Area	Action
1	0 (1)	8 (7)	8	1	8	1 < 7. Move L++
2	1 (8)	8 (7)	7	7	49	8 >= 7. Move R--
3	1 (8)	7 (3)	6	3	18	8 >= 3. Move R--
4	1 (8)	6 (8)	5	8	40	8 >= 8. Move R--

The pointers keep closing until they meet, and no later container beats the 49 found at step 2, so the answer is 49.

The Solution Template

def max_area(height):
left = 0
right = len(height) - 1
max_area = 0

while left < right:
    # Calculate current area
    width = right - left
    h = min(height[left], height[right])
    max_area = max(max_area, width * h)
    
    # Move the pointer of the shorter line
    if height[left] < height[right]:
        left += 1
    else:
        right -= 1
        
return max_area

Container With Most Water Code

1function maxArea(height) {
2    let left = 0;
3    let right = height.length - 1;
4    let maxArea = 0;
5
6    while (left < right) {
7        const w = right - left;
8        const h = Math.min(height[left], height[right]);
9        maxArea = Math.max(maxArea, w * h);
10
11        if (height[left] < height[right]) left++;
12        else right--;
13    }
14    return maxArea;
15}

Edge Cases & Common Mistakes

Edge Case Checklist:

Less than 2 lines: Cannot form a container. Return 0.
All zeros: Max area is 0.
Equal Heights: Doesn't matter which one you move, but standard is to move right pointer.

Common Mistakes:

Moving the Taller Line: Intuition might say "keep the tall one", but if you move the tall one, the short one still limits the height, and width decreases. You LOSE area. You MUST move the shorter one to have a chance of finding a taller counterpart.

Summary

Recap:

Key Insight: The area is limited by the shorter line.
Strategy: Start max width, then greedily eliminate the shorter line to try and find a taller one.
Result: Efficient O(n) scan instead of O(n^2).

Longest Palindromic Substring

3-Sum