3Sum

What it tests

Composing sort + two pointers, and the fiddly part: skipping duplicates.

Approach & answer

Sort first. Fix each index i, then two-pointer the rest for pairs summing to −nums[i]. Skip duplicate values at i, and after finding a triplet skip duplicate lo/hi values — that's what keeps triplets unique. Sorting (O(n log n)) unlocks the two-pointer scan and makes dedup a simple 'skip equal neighbors' check instead of a hash set of tuples. Total O(n²), which is optimal for 3Sum. The generalization: k-sum reduces to (k−1)-sum by fixing one element and recursing, bottoming out at the two-pointer base case.

Use this technique when

Any k-sum / triplet problem: sort, fix one, two-pointer the remainder.

Complexity

Time O(n²) · Space O(1) extra (excluding output)

References

• LeetCode 15 · 3Sum
• LeetCode 18 · 4Sum