CODING CHALLENGE · N°28

3Sum

Medium Two PointersArraysInterview Classic

The rite of passage: find every unique triplet summing to zero without drowning in duplicates or O(n³). Sort once, fix one element, and let two pointers squeeze the rest — the pattern that generalizes to a whole family of k-sum problems.

The problem

Given nums, return all unique triplets [a, b, c] with a + b + c = 0. Each triplet must be sorted ascending, the list of triplets sorted lexicographically, and no triplet may appear twice — even if the input contains duplicates.

EXAMPLE 1

Input nums = [-1, 0, 1, 2, -1, -4]

Output [[-1, -1, 2], [-1, 0, 1]]

the duplicate -1 creates one extra triplet, not two copies

EXAMPLE 2

Input nums = [0, 0, 0, 0]

Output [[0, 0, 0]]

once, not four times

EXAMPLE 3

Input nums = [1, 2, 3]

Output []

no zero-sum triplet

CONSTRAINTS

Triplets sorted ascending internally; the result list sorted lexicographically.
No duplicate triplets in the output.
Target O(n²): sort + fixed element + two pointers, not three nested loops.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement three_sum(nums) → all unique zero-sum triplets, using sort + two pointers and duplicate-skipping at every level.

HINTS — 4 IDEAS

Sort first. Sorted order is what makes both the two pointers AND the dedup possible.
Fix index i; find pairs in nums[i+1:] summing to -nums[i] with left/right pointers.
Sum too small → move left up; too big → move right down; equal → record and move BOTH.
Skip duplicates three times: at i, at left after a hit, at right after a hit.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Sort the array first. Then fix each element a[i] and run a two-pointer sweep over the rest to find pairs summing to −a[i]: a left pointer just after i, a right pointer at the end, moving them inward based on whether the sum is too small or too large. Skip duplicate values at every level so you never emit the same triplet twice.

Complexity

Time O(n²) — an O(n) two-pointer pass inside the O(n) outer loop, after an O(n log n) sort; space O(1) beyond the output.

Common mistakes

Brute-forcing all triples in O(n³) instead of collapsing the inner search with two pointers.
Not skipping duplicates, so the result contains repeated triplets.
Advancing only one pointer on a match, or forgetting to move past duplicate values after recording one.

Where this shows up

Three-sum is the canonical “sort, then two pointers to collapse a dimension” pattern — trading an O(n³) search for O(n²) by exploiting order. The same reduction recurs across pair-, triple-, and k-sum problems and in any search where sortedness lets you prune half the space each step.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA