DSA-016 · Two-pointer elimination

Container With Most Water

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 21848 deterministic checks. Learner drafts are not executed.

Understand the problem

Choose two vertical lines from a nonnegative height array to maximize the area between them and the horizontal axis. Return the greatest area; do not reorder lines.

Non-null int[] of length 0–100,000; heights are 0–1,000,000,000. Fewer than two lines returns 0.
For i<j, area=(j-i)×min(height[i],height[j]); slanted containers and rearrangements are not allowed.
Return long because area can exceed int range. Preserve input. Only area is required, so ties need no index policy.

Examples

Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Indices 1 and 8 have width 7 and limiting height 7.
Input: [1,1]
Output: 1
Width one times height one.
Input: [1000000000,0,0,1000000000]
Output: 3000000000
Cast before multiplication to retain the full area.

Before you start

Area as width times shorter height
Proving a discarded candidate cannot improve the answer

Recognize the structure

A pair of boundaries determines an area, and reducing width must be compensated by increasing the shorter height. This supports a safe elimination rule. It is not the trapping-rain-water problem, which sums many cells instead of choosing one pair.

Try before revealing

Hint 1

Can a smaller width help if the limiting height stays the same?

Hint 2

Fix the shorter boundary and compare it with all interior partners.

Hint 3

Record the area and move the shorter side inward.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Check every pair

For each left line, examine every line to its right. On [1,2,1], areas are 1,2,1 and the maximum is 2. There are n(n-1)/2 pairs, each checked in O(1), so time is O(n²) and workspace O(1). The bottleneck is testing pairs that are already dominated.

Improve the baseline

Start with maximum width

Put left at 0 and right at n-1. Record the current area before moving a boundary.

Discard the shorter boundary

If height[left]≤height[right], every container using left and an interior right boundary has smaller width and limiting height at most height[left]. None can beat the pair just measured.

Repeat symmetrically

Move right when it is shorter. With equal heights either side can be discarded; this reference moves left. Each move reduces the search interval.

Why it is correct

Initialize

Every pair is initially available between the two boundaries; best=0 is a valid lower bound.

Preserve

Measure the boundary pair and store its area. The shorter-boundary argument proves every newly discarded pair has area no greater than an already measured pair. Thus any unmeasured improvement must lie within the remaining interval.

Terminate

One pointer moves each iteration, so eventually left≥right and no pair remains. Every discarded pair is dominated by a measured one; best is therefore optimal.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    public static long maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        long best = 0;
        while (left < right) {
            long area = (long) (right - left) * Math.min(height[left], height[right]);
            best = Math.max(best, area);
            if (height[left] <= height[right]) left++;
            else right--;
        }
        return best;
    }

    public static long baseline(int[] height) {
        long best = 0;
        for (int i = 0; i < height.length; i++)
            for (int j = i + 1; j < height.length; j++)
                best = Math.max(best, (long) (j - i) * Math.min(height[i], height[j]));
        return best;
    }
}

Read the meaningful blocks

Widen arithmetic first

Cast width to long before multiplying by the limiting height.

Record before moving

The eliminated pairs are dominated by this particular measured pair, so recording it is part of the proof.

Move one boundary

Choose the shorter side; moving the taller one has no elimination justification.

Complexity

O(n) time: at most n-1 pointer moves. O(1) auxiliary space and one long output. No sorting or copying is needed.

The pair baseline is O(n²) time with the same constant workspace. The improved method eliminates work rather than caching it.

Exact-state walkthroughs

Reveal normal and boundary traces

Move the limiting boundary

Input: [1,2,4,3] · Result: 4

Step 1 of 8: Begin with the widest pair.

Every unmeasured improvement lies within these boundaries.

Original array indices and values

0: 1
1: 2
2: 4
3: 3

State after this step
Variable	Value
height	`[1,2,4,3]`
left	`0`
right	`3`
best	`0`

See the affected Java block

 1 public final class Solution {
 2     public static long maxArea(int[] height) {
 3         int left = 0, right = height.length - 1;
 4         long best = 0;
 5         while (left < right) {
 6             long area = (long) (right - left) * Math.min(height[left], height[right]);
 7             best = Math.max(best, area);
 8             if (height[left] <= height[right]) left++;
 9             else right--;
10         }
11         return best;
12     }
13 
14     public static long baseline(int[] height) {
15         long best = 0;
16         for (int i = 0; i < height.length; i++)
17             for (int j = i + 1; j < height.length; j++)
18                 best = Math.max(best, (long) (j - i) * Math.min(height[i], height[j]));
19         return best;
20     }
21 }
22

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin with the widest pair.
Every unmeasured improvement lies within these boundaries.
height
[1,2,4,3]
left
0
right
3
best
0
Measure before discarding a boundary.
best includes the pair that dominates candidates about to be discarded.
left
0
right
3
leftHeight
1
rightHeight
3
area
3
best
3
Discard a shorter boundary.
Discarded pairs cannot beat the pair just measured.
left
1
right
3
best
3
Measure before discarding a boundary.
best includes the pair that dominates candidates about to be discarded.
left
1
right
3
leftHeight
2
rightHeight
3
area
4
best
4
Discard a shorter boundary.
Discarded pairs cannot beat the pair just measured.
left
2
right
3
best
4
Measure before discarding a boundary.
best includes the pair that dominates candidates about to be discarded.
left
2
right
3
leftHeight
4
rightHeight
3
area
3
best
4
Discard a shorter boundary.
Discarded pairs cannot beat the pair just measured.
left
2
right
2
best
4
Return the contract result.
The final state satisfies the requested output contract.
result
4

Equal zero heights

Input: [0,0,0] · Result: 0

Step 1 of 6: Begin with the widest pair.

Every unmeasured improvement lies within these boundaries.

Original array indices and values

0: 0
1: 0
2: 0

State after this step
Variable	Value
height	`[0,0,0]`
left	`0`
right	`2`
best	`0`

See the affected Java block

 1 public final class Solution {
 2     public static long maxArea(int[] height) {
 3         int left = 0, right = height.length - 1;
 4         long best = 0;
 5         while (left < right) {
 6             long area = (long) (right - left) * Math.min(height[left], height[right]);
 7             best = Math.max(best, area);
 8             if (height[left] <= height[right]) left++;
 9             else right--;
10         }
11         return best;
12     }
13 
14     public static long baseline(int[] height) {
15         long best = 0;
16         for (int i = 0; i < height.length; i++)
17             for (int j = i + 1; j < height.length; j++)
18                 best = Math.max(best, (long) (j - i) * Math.min(height[i], height[j]));
19         return best;
20     }
21 }
22

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin with the widest pair.
Every unmeasured improvement lies within these boundaries.
height
[0,0,0]
left
0
right
2
best
0
Measure before discarding a boundary.
best includes the pair that dominates candidates about to be discarded.
left
0
right
2
leftHeight
0
rightHeight
0
area
0
best
0
Discard a shorter boundary.
Discarded pairs cannot beat the pair just measured.
left
1
right
2
best
0
Measure before discarding a boundary.
best includes the pair that dominates candidates about to be discarded.
left
1
right
2
leftHeight
0
rightHeight
0
area
0
best
0
Discard a shorter boundary.
Discarded pairs cannot beat the pair just measured.
left
2
right
2
best
0
Return the contract result.
The final state satisfies the requested output contract.
result
0

Test the contract

Input: []
Output: 0
No lines.
Input: [5]
Output: 0
One line.
Input: [0,0,0]
Output: 0
No positive height.
Input: [3,3,3]
Output: 6
Equal endpoints permit either move.

Common mistakes and counterexamples

Move the taller side

Counterexample: [1,2,4,3] can discard the optimal pair at indices 1 and 3.

Discard a shorter boundary only.

Use the taller height in area

Counterexample: [1,10] holds area 1, not 10.

Water height is limited by the shorter line.

Multiply as int then cast

Counterexample: [1000000000,0,0,1000000000] overflows int.

Cast before multiplication.

Follow-ups

Return one optimal pair.

Store the two indices on improvement. Specify a tie policy; if all equal-area ties must be enumerated, this simple discard rule may skip ties and needs reconsideration.

Heights arrive in a stream.

Two-pointer access needs both ends. Explain why retaining just the current best pair is insufficient; a future line can pair with an older discarded candidate.

Now compute trapped rainwater.

This asks for volume over many indices, not one rectangle. Derive per-index limiting maxima or a separate two-pointer water-level invariant.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 95/20,000 characters

Self-review

I can prove the shorter-side elimination.I record the area before moving.I use long multiplication and preserve positions.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Two pointers: eliminate with a proof

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-14 · Original explanations, examples, and Java implementations for AceYourInterviews. Familiar task names identify standard algorithmic problems; no company-frequency claims are made.