DSA-016 · FOCUSED PRACTICE
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:49Indices 1 and 8 have width 7 and limiting height 7.
Input:
[1,1]
Output:1Width one times height one.
Input:
[1000000000,0,0,1000000000]
Output:3000000000Cast 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.
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.
No unsaved text changes · 95/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
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.
- 0: 1
- 1: 2
- 2: 4
- 3: 3
| 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.
- 0: 0
- 1: 0
- 2: 0
| 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:0No lines.
Input:
[5]
Output:0One line.
Input:
[0,0,0]
Output:0No positive height.
Input:
[3,3,3]
Output:6Equal 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.