Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Return all unique triplets that sum to zero. The interview-grade answer is: sort the array, fix one number with an outer loop, then two-pointer the rest of the array for the remaining pair that sums to its negation. Skip duplicate values at every level to keep triplets unique. O(n²) time, O(1) extra space (ignoring the output and sort).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you reduce a triple-sum to a fixed element plus a sorted two-pointer Two Sum, and whether you can dedupe triplets cleanly without a hash set on the output.
Where candidates slip
Producing duplicate triplets (e.g. forgetting to skip equal anchors or equal pointer values), or defaulting to a brute-force O(n³) triple loop.
How to stand out
State the O(n³) brute force, then 'sorting lets me fix one and two-pointer the rest for O(n²)'. Explain each duplicate-skip and the early break when nums[i] > 0.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewAll unique triplets summing to zeroCan I sort? (values, not indices)NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Triple Loop With a Dedupe Set
1Hint 1Explore hintHide hint
The most literal reading: try every combination of three distinct indices and keep the ones that sum to zero.
2Hint 2Explore hintHide hint
Three nested loops i < j < k. For each triple, test nums[i] + nums[j] + nums[k] == 0.
3Hint 3Explore hintHide hint
To avoid duplicate triplets, sort each found triplet and store it in a set before collecting — but notice that's a lot of wasted work.
A · Core idea
Enumerate every triple of indices i < j < k and keep those whose values sum to zero. Because the same triplet of values can arise from different index combinations, normalize each hit (sort its three numbers) and store it in a set so duplicates collapse.
Why this is the natural first attempt. 'Three numbers that sum to zero' maps directly to three nested loops. It's obviously correct, and stating it shows you can establish a baseline before reaching for cleverness.
Why the dedupe is awkward. The brute force has no structure to exploit, so the only way to keep triplets unique is to canonicalize each one (sort it) and dump it into a hash set. That's extra time per triplet and O(n) extra memory — a smell that the algorithm is fighting the problem rather than using it.
Why we don't ship this. With n = 3000, n³/6 is about 4.5 billion iterations — far too slow. The cubic factor and the bolt-on dedupe are exactly what sorting eliminates: once sorted, duplicates sit next to each other and the inner pair search collapses to two pointers.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [-1, 0, 1, -1]i=0,j=1,k=2
-1 + 0 + 1 = 0
set = {(-1,0,1)}[[-1, 0, 1]]C · Code with teaching comments
Reference implementation previewpublic List<List<Integer>> threeSum(int[] nums) { Set<List<Integer>> found = new HashSet<>(); int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) {Explore the full codeHide the full code
D · Why it works and complexityO(n³) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The brute force needs a set purely to fight duplicates. That pain is the signal: if the data were sorted, equal values would be adjacent and dedupe would be a cheap neighbour comparison — which is the whole reason the optimal sorts first.
ComplexityO(n³) time, O(n) space — Choosing 3 of n indices is C(n,3) ≈ n³/6 combinations. Sorting each triplet and hashing it into a set adds the O(n) space for the dedupe structure.
E · Edge cases and pitfalls3Returning duplicate triplets because you forgot to canonicalize before adding to the set.Explore edge casesHide edge cases
Pitfalls
- Returning duplicate triplets because you forgot to canonicalize before adding to the set.
- Letting loops reuse an index (j starting at i instead of i+1).
- Shipping O(n³) when n can be 3000 — it will time out.
Approach 2 of 2 · Optimal
Sort + Two Pointers (Optimal)
1Hint 1Explore hintHide hint
If the array were sorted, finding a pair that sums to a target is O(n) with two pointers (Two Sum II). How can you reuse that for a triple?
2Hint 2Explore hintHide hint
Sort the array. Fix the first element nums[i]; now you need two more numbers summing to -nums[i] in the suffix — exactly sorted Two Sum.
3Hint 3Explore hintHide hint
Walk l from i+1 and r from the end: move l up if the sum is too small, r down if too big. After a hit, skip equal neighbours on both pointers (and skip equal anchors) to avoid duplicate triplets.
A · Core idea
Sort the array first. Then iterate an anchor index i from left to right. For each anchor, the remaining problem is 'find two numbers in the suffix i+1 .. n-1 that sum to -nums[i]' — and because the suffix is sorted, that's a classic two-pointer scan with l = i+1 and r = n-1.
Why sorting is the unlock. Two Sum on an unsorted array needs a hash map. But on a sorted array, two pointers solve it in O(1) space: if the current sum is too small, the only way to grow it is to move the left pointer right (to a larger value); if it's too big, move the right pointer left. Sortedness makes the search monotonic, so each pointer sweeps the suffix once. Wrapping that in the outer anchor loop turns an O(n³) problem into O(n²).
How duplicates are killed, level by level. Sorting places equal values next to each other, so dedupe becomes neighbour comparison instead of a hash set:
- Anchor dedupe: if
nums[i] == nums[i-1], this anchor would reproduce every triplet the previous anchor already found — skip it. - Pointer dedupe: after recording a triplet, advance
lpast any values equal to the one just used, and pullrback past any equal values, so the same pair isn't recorded twice.
Why the early break helps. Once nums[i] > 0, the anchor and everything to its right are positive (array is sorted), so no triplet starting here can sum to zero. Breaking out skips a chunk of useless work.
Why O(1) extra space. We sort in place and use only the indices i, l, r. The returned list isn't counted as auxiliary space, and unlike the brute force we need no dedupe set.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [-1, 0, 1, 2, -1, -4]Array state
l=2, r=5
-1 + (-1) + 2 = 0 ✓ record [-1,-1,2]
[[-1, -1, 2], [-1, 0, 1]]C · Code with teaching comments
D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
3Sum = an outer loop over Two Sum II. The two reusable moves — 'sort to convert a hash-map pair search into an O(1)-space two-pointer scan' and 'skip equal neighbours to dedupe' — generalize directly: add another outer loop and the same machinery solves 4Sum in O(n³).
ComplexityO(n²) time, O(1) space — Sorting is O(n log n). The outer loop runs n times and each inner two-pointer scan is O(n), giving O(n²) which dominates. Aside from the output and the in-place sort, only a few indices are stored → O(1) extra space.
E · Edge cases and pitfalls6nums = [0, 0, 0, 0] — Anchor at first 0 finds [0,0,0]; the equal-anchor skip prevents recording it again from later zeros.Explore edge casesHide edge cases
Edge cases handled
nums = [0, 0, 0, 0]Anchor at first 0 finds [0,0,0]; the equal-anchor skip prevents recording it again from later zeros.nums = [1, 2, 3]All positive; nums[0]=1 > 0 triggers the early break → returns [].nums = [-2, 0, 1, 1, 2]Finds [-2,0,2] and [-2,1,1]; pointer dedupe ensures the repeated 1 doesn't double-record.
Pitfalls
- Forgetting any of the three duplicate skips → duplicate triplets in the output.
- Skipping the anchor with `i >= 0` instead of `i > 0` — skips the very first element wrongly.
- Comparing nums[l] to nums[l+1] (not yet visited) instead of nums[l-1] when deduping after the move.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n - 2; i++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Not skipping the duplicate anchor
If two equal anchors are processed, every triplet found for the first is regenerated for the second, producing duplicates.
Explore the code comparisonHide the code comparison
Not skipping the duplicate anchor
If two equal anchors are processed, every triplet found for the first is regenerated for the second, producing duplicates.
Don't write this
for i in range(n - 2):
l, r = i + 1, n - 1
# ... no anchor dedupe ...Write this instead
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, n - 12Not deduping the pointers after a hit
When the suffix has repeated values, the same (l, r) value pair can be recorded multiple times unless you skip equal neighbours.
Explore the code comparisonHide the code comparison
Not deduping the pointers after a hit
When the suffix has repeated values, the same (l, r) value pair can be recorded multiple times unless you skip equal neighbours.
Don't write this
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
l++;
r--;Write this instead
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
l++;
r--;
while (l < r && nums[l] == nums[l - 1]) l++;
while (l < r && nums[r] == nums[r + 1]) r--;3Forgetting to sort before two pointers
The two-pointer convergence relies on monotonic sums; on an unsorted array, moving l or r doesn't reliably grow or shrink the sum.
Explore the code comparisonHide the code comparison
Forgetting to sort before two pointers
The two-pointer convergence relies on monotonic sums; on an unsorted array, moving l or r doesn't reliably grow or shrink the sum.
Don't write this
res = []
for i in range(n - 2):
l, r = i + 1, n - 1 # array never sorted!Write this instead
nums.sort()
res = []
for i in range(n - 2):
l, r = i + 1, n - 1Revise
Carry the pattern into the interview
Pattern to remember
Sort + fix one + two pointers, skip duplicates
Code pattern to memorize
sort(nums)
for i in range(n):
if i > 0 and nums[i] == nums[i-1]: continue # skip dup anchor
l, r = i+1, n-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0: l += 1
elif s > 0: r -= 1
else: record; skip dup l and r; l += 1; r -= 1Rules to remember
- 1Sort first — it's what enables two pointers and makes duplicate-skipping trivial.
- 2Skip a duplicate anchor with
if i > 0 and nums[i] == nums[i-1]: continue. - 3After recording a triplet, skip duplicate
landrvalues before moving both pointers. - 4Move
lright when the sum is too small,rleft when too big — sortedness makes this monotonic. - 5Break early once
nums[i] > 0: with a sorted array, three non-negative numbers can't sum to zero.
Use this pattern when
- Find triplets / k-tuples that hit a target sum
- Array is unsorted but you're allowed to sort (indices don't matter — values do)
- You need *all unique* combinations, not just one match
- A nested-loop pair search inside a fixed element can be collapsed with two pointers
Choose another pattern when
- Need the original indices, not values → sorting destroys them; use a hash map (that's Two Sum)
- Only one pair, not all triplets → Two Sum hash map is simpler
- Array already sorted and you need a single pair → plain two pointers (Two Sum II)
Interview takeaway
3Sum is Two Sum II wrapped in an outer loop: fix one number, then solve a sorted two-pointer Two Sum for its negative. The reusable moves are 'sort to unlock two pointers' and 'skip equal neighbours to dedupe' — they extend straight to 4Sum and 3Sum Closest.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternSort + fix-one + two-pointer for k-sum problems. Recognise it whenever you need all unique tuples hitting a target sum and indices don't matter. Same family as Two Sum II, 3Sum Closest, and 4Sum.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Two SumThe pair-finding core, but unsorted and returning indices — use a hash map instead of two pointers.
- Two Sum II — Sorted ArrayExactly the inner two-pointer scan of 3Sum, standalone on a sorted array.
- 3Sum ClosestComing soonSame sort + two-pointer skeleton, but track the sum closest to target instead of exactly zero.
- 4SumComing soonAdd a second outer loop — two fixed anchors, two-pointer the remaining pair. O(n³).