vizlearn

3Sum

Interview QuestionsBy Updated

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.

Overview

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.

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."

3Sum

Find all unique triples in an array that sum to zero.

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.

Run it in Python

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

three_sum.pyPython 3
Output
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
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.
INTERVIEW · vizlearn.in/interview/three-sum.html
More in Interview
InterviewSearch in a rotated sorted arrayInterviewSliding window maximumInterviewlist vs tuple vs deque vs array — which and why?InterviewHow does a Python dict work?
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.
About VizLearnGitHubLinkedInContact