DSA-015 · Sorted anchor plus duplicate-aware two pointers

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.

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.

Sorted clone — anchor and endpoints

0: -4
1: -1
2: -1
3: 0
4: 1
5: 2

State after this step
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.

Sorted clone — anchor and endpoints

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

State after this step
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.

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 · 98/20,000 characters

Self-review

I distinguish values from indices.I prove duplicate skipping preserves completeness.I account for the cloned input and output size.

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-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.