DSA-015 · FOCUSED PRACTICE
3Sum
Advanced · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 20536 deterministic checks. Learner drafts are not executed.
Understand the problem
Return every distinct nondecreasing value triple whose values occur at three distinct input positions and sum to zero.
- nums is non-null with 0–3,000 signed int entries. Input order is arbitrary and must be preserved; the optimized method sorts a clone.
- Return List<List<Integer>>. Each triple is nondecreasing, sums mathematically to zero, and respects input multiplicities. Return each value triple once; outer list ordering is unspecified. Empty output is valid.
- Use long arithmetic for the three-value sum. Separate sorting workspace, cloned input, and potentially quadratic output storage. The cubic baseline is for small inputs in tests and teaching, not the maximum-sized workload.
Examples
Input:
[-1,0,1,2,-1,-4]
Output:[[-1,-1,2],[-1,0,1]]The two -1 occurrences can occupy distinct indices; repeated discovery of the same values is suppressed.
Input:
[0,0,0,0]
Output:[[0,0,0]]Four index triples represent one value triple.
Before you start
- Array indexing and inclusive pointer bounds
- Loop invariants and Java value versus reference semantics
Recognize the structure
Fixing the smallest value of a sorted triple reduces the remaining task to sorted two-sum. The challenge has two layers: eliminate impossible pairs without losing answers, and avoid repeating the same value triple.
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 · 98/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Fix one value and solve a two-sum task on the remaining suffix.
Hint 2
How can sorted order prove each pointer move safe?
Hint 3
Skip repeated anchors; after a hit skip both equal partner runs.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate and canonicalize triples
Enumerate i<j<k, test the long sum, sort each qualifying triple, and insert it into a set. On [0,0,0,0], four position combinations all canonicalize to [0,0,0], leaving one result. This takes O(n³) time plus answer-set storage; it is an independent small-input baseline.
Improve the baseline
Sort a protected copy
Sorting groups duplicates and imposes an order so the first selected value is the smallest in a result triple. Clone before sorting to preserve the caller’s array.
Scan one suffix per anchor value
For each new anchor value, initialize left=anchor+1 and right=n-1. Move left on a negative long sum and right on a positive sum.
Emit once and skip equal partners
On zero, emit the three values, remember both partner values, and skip their equal runs. Skip repeated anchor values at the outer loop so no result is emitted again under the same smallest value.
Why it is correct
Completeness per anchor
For a fixed anchor, a negative sum rules out the current left with every smaller right, and a positive sum rules out the current right with every larger left. These monotone eliminations preserve every still-unseen feasible value pair.
Safe duplicate suppression
Equal anchor values have identical value-level search tasks; the first occurrence has the largest available suffix. After a hit, another identical left or right partner can only reproduce that same zero-sum partner pair. Skipping its run removes no new value triple.
Uniqueness and termination
Each triple has one smallest anchor value and one partner value pair. Both duplicate filters prevent repeats. Each pointer moves inward and every anchor advances, so the algorithm terminates after O(n²) pointer work.
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.
import java.util.*;
public final class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
List<List<Integer>> answer = new ArrayList<>();
for (int anchor = 0; anchor + 2 < sorted.length; anchor++) {
if (anchor > 0 && sorted[anchor] == sorted[anchor - 1]) continue;
int left = anchor + 1, right = sorted.length - 1;
while (left < right) {
long sum = (long) sorted[anchor] + sorted[left] + sorted[right];
if (sum < 0) left++;
else if (sum > 0) right--;
else {
answer.add(List.of(sorted[anchor], sorted[left], sorted[right]));
int lowValue = sorted[left], highValue = sorted[right];
while (left < right && sorted[left] == lowValue) left++;
while (left < right && sorted[right] == highValue) right--;
}
}
}
return answer;
}
public static List<List<Integer>> baseline(int[] nums) {
Set<List<Integer>> unique = new HashSet<>();
for (int i = 0; i < nums.length; i++) for (int j = i + 1; j < nums.length; j++) for (int k = j + 1; k < nums.length; k++) {
if ((long) nums[i] + nums[j] + nums[k] == 0) {
int[] triple = {nums[i], nums[j], nums[k]}; Arrays.sort(triple);
unique.add(List.of(triple[0], triple[1], triple[2]));
}
}
return new ArrayList<>(unique);
}
}
Read the meaningful blocks
Start after anchor
This enforces three distinct positions even when all three values are equal.
Cast the first addend
A long sum avoids false zero from int overflow, for example two maximum ints plus 2.
Remember duplicate values
Store lowValue and highValue before moving. Run skipping must remain bounded by left<right; an empty remaining pair interval is normal.
Complexity
O(n²) total time, including O(n log n) sorting; O(n) cloned storage plus sorting workspace. The Java primitive sort’s internal workspace is not part of a claimed O(1) total auxiliary bound here.
There can be O(n²) distinct result triples, so output storage is O(k) for k returned triples. The cubic baseline also retains a set of up to k canonical triples and is intended only for small comparisons.
Exact-state walkthroughs
Reveal normal and boundary traces
Anchor and partner duplicate suppression
Input: [-1,0,1,2,-1,-4] · Result: [[-1,-1,2],[-1,0,1]]
Step 1 of 13: Sort a clone and preserve the original input.
Each result will have a smallest anchor followed by two suffix positions.
- 0: -4
- 1: -1
- 2: -1
- 3: 0
- 4: 1
- 5: 2
| Variable | Value |
|---|---|
| values | [-4,-1,-1,0,1,2] |
| triples | [] |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static List<List<Integer>> threeSum(int[] nums) { 4 int[] sorted = nums.clone(); 5 Arrays.sort(sorted); 6 List<List<Integer>> answer = new ArrayList<>(); 7 for (int anchor = 0; anchor + 2 < sorted.length; anchor++) { 8 if (anchor > 0 && sorted[anchor] == sorted[anchor - 1]) continue; 9 int left = anchor + 1, right = sorted.length - 1; 10 while (left < right) { 11 long sum = (long) sorted[anchor] + sorted[left] + sorted[right]; 12 if (sum < 0) left++; 13 else if (sum > 0) right--; 14 else { 15 answer.add(List.of(sorted[anchor], sorted[left], sorted[right])); 16 int lowValue = sorted[left], highValue = sorted[right]; 17 while (left < right && sorted[left] == lowValue) left++; 18 while (left < right && sorted[right] == highValue) right--; 19 } 20 } 21 } 22 return answer; 23 } 24 public static List<List<Integer>> baseline(int[] nums) { 25 Set<List<Integer>> unique = new HashSet<>(); 26 for (int i = 0; i < nums.length; i++) for (int j = i + 1; j < nums.length; j++) for (int k = j + 1; k < nums.length; k++) { 27 if ((long) nums[i] + nums[j] + nums[k] == 0) { 28 int[] triple = {nums[i], nums[j], nums[k]}; Arrays.sort(triple); 29 unique.add(List.of(triple[0], triple[1], triple[2])); 30 } 31 } 32 return new ArrayList<>(unique); 33 } 34 } 35
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Sort a clone and preserve the original input.
Each result will have a smallest anchor followed by two suffix positions.
- values
[-4,-1,-1,0,1,2]- triples
[]
- Search the suffix for this anchor.
Every remaining pair uses distinct positions strictly after anchor.
- values
[-4,-1,-1,0,1,2]- anchor
0- left
1- right
5- triples
[]
- Eliminate an impossible pair endpoint.
Sorted order proves every discarded pair using the chosen endpoint misses zero.
- values
[-4,-1,-1,0,1,2]- anchor
0- oldLeft
1- oldRight
5- left
2- right
5- sum
-3- triples
[]
- Eliminate an impossible pair endpoint.
Sorted order proves every discarded pair using the chosen endpoint misses zero.
- values
[-4,-1,-1,0,1,2]- anchor
0- oldLeft
2- oldRight
5- left
3- right
5- sum
-3- triples
[]
- Eliminate an impossible pair endpoint.
Sorted order proves every discarded pair using the chosen endpoint misses zero.
- values
[-4,-1,-1,0,1,2]- anchor
0- oldLeft
3- oldRight
5- left
4- right
5- sum
-2- triples
[]
- Eliminate an impossible pair endpoint.
Sorted order proves every discarded pair using the chosen endpoint misses zero.
- values
[-4,-1,-1,0,1,2]- anchor
0- oldLeft
4- oldRight
5- left
5- right
5- sum
-1- triples
[]
- Search the suffix for this anchor.
Every remaining pair uses distinct positions strictly after anchor.
- values
[-4,-1,-1,0,1,2]- anchor
1- left
2- right
5- triples
[]
- Emit the value triple once and skip equal partner runs.
Equal partner occurrences would only repeat this triple.
- values
[-4,-1,-1,0,1,2]- anchor
1- oldLeft
2- oldRight
5- left
3- right
4- sum
0- triples
[[-1,-1,2]]
- Emit the value triple once and skip equal partner runs.
Equal partner occurrences would only repeat this triple.
- values
[-4,-1,-1,0,1,2]- anchor
1- oldLeft
3- oldRight
4- left
4- right
4- sum
0- triples
[[-1,-1,2],[-1,0,1]]
- Skip an already-owned anchor value.
The first equal anchor already searched a superset of this suffix.
- values
[-4,-1,-1,0,1,2]- anchor
2- triples
[[-1,-1,2],[-1,0,1]]
- Search the suffix for this anchor.
Every remaining pair uses distinct positions strictly after anchor.
- values
[-4,-1,-1,0,1,2]- anchor
3- left
4- right
5- triples
[[-1,-1,2],[-1,0,1]]
- Eliminate an impossible pair endpoint.
Sorted order proves every discarded pair using the chosen endpoint misses zero.
- values
[-4,-1,-1,0,1,2]- anchor
3- oldLeft
4- oldRight
5- left
4- right
4- sum
3- triples
[[-1,-1,2],[-1,0,1]]
- Return the contract result.
All required values have been finalized under the declared contract.
- result
[[-1,-1,2],[-1,0,1]]
One triple from repeated zeros
Input: [0,0,0,0] · Result: [[0,0,0]]
Step 1 of 5: Sort a clone and preserve the original input.
Each result will have a smallest anchor followed by two suffix positions.
- 0: 0
- 1: 0
- 2: 0
- 3: 0
| Variable | Value |
|---|---|
| values | [0,0,0,0] |
| triples | [] |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static List<List<Integer>> threeSum(int[] nums) { 4 int[] sorted = nums.clone(); 5 Arrays.sort(sorted); 6 List<List<Integer>> answer = new ArrayList<>(); 7 for (int anchor = 0; anchor + 2 < sorted.length; anchor++) { 8 if (anchor > 0 && sorted[anchor] == sorted[anchor - 1]) continue; 9 int left = anchor + 1, right = sorted.length - 1; 10 while (left < right) { 11 long sum = (long) sorted[anchor] + sorted[left] + sorted[right]; 12 if (sum < 0) left++; 13 else if (sum > 0) right--; 14 else { 15 answer.add(List.of(sorted[anchor], sorted[left], sorted[right])); 16 int lowValue = sorted[left], highValue = sorted[right]; 17 while (left < right && sorted[left] == lowValue) left++; 18 while (left < right && sorted[right] == highValue) right--; 19 } 20 } 21 } 22 return answer; 23 } 24 public static List<List<Integer>> baseline(int[] nums) { 25 Set<List<Integer>> unique = new HashSet<>(); 26 for (int i = 0; i < nums.length; i++) for (int j = i + 1; j < nums.length; j++) for (int k = j + 1; k < nums.length; k++) { 27 if ((long) nums[i] + nums[j] + nums[k] == 0) { 28 int[] triple = {nums[i], nums[j], nums[k]}; Arrays.sort(triple); 29 unique.add(List.of(triple[0], triple[1], triple[2])); 30 } 31 } 32 return new ArrayList<>(unique); 33 } 34 } 35
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Sort a clone and preserve the original input.
Each result will have a smallest anchor followed by two suffix positions.
- values
[0,0,0,0]- triples
[]
- Search the suffix for this anchor.
Every remaining pair uses distinct positions strictly after anchor.
- values
[0,0,0,0]- anchor
0- left
1- right
3- triples
[]
- Emit the value triple once and skip equal partner runs.
Equal partner occurrences would only repeat this triple.
- values
[0,0,0,0]- anchor
0- oldLeft
1- oldRight
3- left
3- right
3- sum
0- triples
[[0,0,0]]
- Skip an already-owned anchor value.
The first equal anchor already searched a superset of this suffix.
- values
[0,0,0,0]- anchor
1- triples
[[0,0,0]]
- Return the contract result.
All required values have been finalized under the declared contract.
- result
[[0,0,0]]
Test the contract
Input:
[]
Output:[]Too few positions.
Input:
[0,0]
Output:[]Three distinct positions are required.
Input:
[-2,0,0,2,2]
Output:[[-2,0,2]]Repeated partners do not repeat the output.
Input:
[-2147483648,1,2147483647]
Output:[[-2147483648,1,2147483647]]Long sum handles extremes exactly.
Common mistakes and counterexamples
Sort the caller’s array
Counterexample: [-1,2,0] would be visibly reordered.
Sort nums.clone().
Skip all equal values before finding a pair
Counterexample: [0,0,0] still needs three occurrences.
Skip duplicate anchors and skip partner runs only after recording a hit.
Use int sum
Counterexample: [2147483647,2147483647,2] wraps to zero in int arithmetic.
Widen before the first addition.
Follow-ups
Return index triples.
Value deduplication is then wrong: duplicate values may create many distinct index combinations. Carry original indices and define output size and ordering separately.
Find the closest sum.
Track the best long distance from a long target, define ties, and move by the sum comparison. Subtracting extreme long targets can itself overflow; use constrained targets or wider comparison logic.
Generalize to kSum.
Recursively fix sorted anchors with duplicate skipping and finish at two-sum. Explain recursion depth, pruning bounds in wide arithmetic, and output-sensitive storage rather than claiming the two-pointer O(n²) bound for every k.