3Sum

Sort, then fix one element and two-pointer the rest. That turns the third loop into a linear scan, so the whole thing is O(n²) rather than O(n³). Sorting also puts duplicates next to each other, which is what makes deduplication a cheap skip instead of a set of tuples.

Lists & arraysCoding problemMedium

Step through it

What to watch

  • One element is fixed; the other two converge.
  • A repeated fixed value is skipped, or the same triple is reported twice.
  • The pointers only ever move inwards — that is the linear inner scan.

Say this out loud

"Sort, then for each index run two pointers over the rest looking for the complement. O(n²) time, O(1) extra space. Sorting also means duplicates are adjacent, so I skip them rather than deduplicating at the end."

Overview

Three Sum returns unique triples whose values add to a target, usually zero. Sorting plus a fixed first value and two pointers reduces the search to O(n²); skipping duplicates is essential to unique output.

In this guide
  1. Run it: 3Sum in code
  2. Sort, then fix one and two-pointer the rest
  3. The duplicate handling, which is the whole difficulty
  4. Reducing the third loop
  5. Deduplication is the real difficulty
  6. The early exits worth mentioning
  7. Tracing the duplicates
  8. Edge cases
  9. The generalisation to k-sum
  10. The variants
  11. Sources and next steps

Run it: 3Sum in code

The two-pointer version against brute force with both operation counts, and the deduplication removed so you can see the duplicate triples it produces.

1Python
Output
2Python
Output
3Python
Output

Sort, then fix one and two-pointer the rest

4Python
Output

O(n²) time — an outer loop with an inner linear scan — and O(1) extra space beyond the output, or O(n) if the sort is counted.

The structure is worth naming: reduce three-sum to n instances of two-sum on a sorted array. Fixing nums[i] turns "find three summing to zero" into "find two summing to -nums[i]". This two pointers solve in O(n).

The duplicate handling, which is the whole difficulty

Three separate skips are needed, and each addresses a different source of repeats.

Duplicate first elements. if i and nums[i] == nums[i-1]: continue. Without it, [-1, -1, 0, 1] produces [-1, 0, 1] twice — once for each -1.

Duplicate second elements. After recording a triplet, advance lo past any repeats. Without it, [-2, 0, 0, 2, 2] produces [-2, 0, 2] several times.

The third element needs no separate skip: with the first two fixed, the third is determined. So no extra duplicate can arise.

The alternative — collecting into a set of sorted tuples — also works and costs O(n) extra space and hides the reasoning. Interviewers usually want the skip version, because it shows understanding of where the duplicates come from.

The if nums[i] > 0: break line is a genuine optimisation rather than a correctness fix: once the smallest of the three is positive, no triplet can reach zero. So the rest of the loop is wasted.

Reducing the third loop

The brute force is three nested loops, O(n³). Fix the first element and the problem becomes "find two numbers summing to -values[i]" — which is Two Sum, and on sorted input Two Sum is two pointers in O(n).

n iterations of an O(n) inner scan is O(n²), and the sort is O(n log n) so it disappears into that. Using a hash map for the inner search is also O(n²), and then deduplication is much harder — which is the argument for sorting.

Deduplication is the real difficulty

Two places need it. Skip a fixed element equal to the previous one, or every triple starting with that value is emitted twice. And after recording a triple, advance past any repeats of both pointer values, or the same triple is found again inside the same scan.

Sorting is what makes both a simple adjacency check. Without it you would collect triples into a set of sorted tuples. Correct, and it allocates for every candidate.

The early exits worth mentioning

Once values[i] > 0 the smallest possible triple is already positive, so the scan can stop entirely. That is not a complexity improvement and it is a large constant on real input.

The generalisation is kSum: fix an element and recurse down to the two-pointer base case, giving O(n^(k−1)). Naming that shows you see the pattern rather than the single problem.

Tracing the duplicates

[-1, 0, 1, 2, -1, -4] sorted becomes [-4, -1, -1, 0, 1, 2].

inums[i]WindowResult
0−4lo=1, hi=5No triplet sums to 0
1−1lo=2, hi=5-1 + -1 + 2 = 0 → record; then -1 + 0 + 1 = 0 → record
2−1—Skipped — same as nums[1]
30lo=4, hi=50 + 1 + 2 = 3 > 0, hi falls to 4, loop ends

Two triplets, no repeats. The skip at i = 2 is what prevents [-1, 0, 1] appearing twice.

Walking that table aloud is a good way to show the solution in an interview, because it exercises exactly the case the duplicate handling exists for.

Edge cases

CaseResult
Fewer than 3 elements[]
All zeros, [0,0,0][[0,0,0]] — one triplet
All zeros, [0,0,0,0][[0,0,0]] — still one, thanks to the skips
All positive[] — caught by the early break
All negative[]
No triplet sums to zero[]
Many duplicatesEach distinct triplet once

The [0,0,0,0] case is the cleanest test of the duplicate logic, and worth mentioning unprompted.

The generalisation to k-sum

The structure extends: fix k−2 elements with nested loops, and two-pointer the last two.

ProblemApproachComplexity
Two-sum, sortedTwo pointersO(n)
Two-sum, unsortedHash mapO(n)
Three-sumOne loop + two pointersO(n²)
Four-sumTwo loops + two pointersO(n³)
k-sumk−2 loops + two pointersO(n^(k−1))

Four-sum has a better alternative worth knowing: hash all pairwise sums, then look for two pairs summing to the target — O(n²) time and O(n²) space, better than O(n³) when memory allows. That trade appears again in the "meet in the middle" technique for subset problems.

The variants

Three-sum closest. Find the triplet whose sum is nearest a target. Same structure, and instead of comparing against zero, track the smallest absolute difference. No duplicate handling needed, because only one answer is returned.

Three-sum smaller. Count triplets with sum below a target. When nums[i] + nums[lo] + nums[hi] < target, every position between lo and hi also works. So add hi - lo and advance lo. That counting shortcut is the insight, and it keeps the whole thing O(n²).

Three-sum with multiplicity. Count the number of index triplets rather than distinct value triplets. A counting problem over value frequencies, with careful case analysis for repeated values.

Two-sum with a target other than zero. Trivially the same code with the comparison adjusted.

Sources and next steps

How the code works

The two-pointer version against brute force with both operation counts, and the deduplication removed so you can see the duplicate triples it produces.

How the code works

  1. if i and values[i] == values[i - 1]: continueThe first deduplication. Without it, every triple beginning with a repeated value is emitted once per repeat.
  2. while lo < hi and values[lo] == values[lo - 1]: lo += 1The second. After recording a triple, both pointers must move past any repeats or the same triple is found again in the same scan.
  3. if values[i] > 0: breakOn sorted input, once the fixed element is positive the smallest possible triple already exceeds zero. Not a complexity change, and a large constant.
  4. lo, hi = i + 1, len(values) - 1The inner search is Two Sum on a sorted range, which is why fixing one element removes an entire loop rather than just reordering the work.

Change one thing

  • Change the target from 0 to 6 by adjusting the comparisons. The structure is unchanged; only the constant moves.
  • Extend it to 4Sum by fixing two elements. O(n³), and the deduplication now needs a skip at both fixed levels.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Check yourself

0 of 3

Answer without scrolling back up.

  1. Fixing one element reduces 3Sum from O(n³) to O(n²) because the inner search becomes:

  2. Why sort rather than use a hash map for the inner search?

  3. How many places need a duplicate skip?

Cheat sheet

3Sum

Find every unique triple that sums to zero. Sort the array, fix one element, and sweep two pointers inward while skipping duplicates at each step.

INTERVIEW · vizlearn.in/interview/three-sum.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.