mediumCodingEntryMidSenior
Return every distinct triplet in the array that sums to zero.
4 min readUpdated 2026-08-15
Answer
Short answer
Sort the array, fix each element as an anchor, then converge two pointers inwards from both ends of the remaining range. The sort is asymptotically free against the O of n squared scan, and it is what lets you skip duplicate values positionally instead of deduplicating a set of results afterwards.
Was this answer helpful?
Likely follow-ups
- Generalise this to k-sum. What is the recurrence for the running time?
- The target is now an arbitrary value rather than zero. Which of your optimisations survive?
- Solve it with hashing instead. Why is deduplication harder that way?
- Find the triplet whose sum is closest to the target rather than equal to it.
Related questions
- Given the heights of a row of bars, work out how much rainwater is trapped between them. Do it in constant extra space.mediumAlso on two-pointers and arrays5 min
- Detect whether a linked list has a cycle, and return the node where the cycle begins.mediumAlso on two-pointers4 min
- Find the length of the longest substring without repeating characters.mediumAlso on two-pointers2 min
- Find the largest sum obtainable from a contiguous run of elements in an array.mediumAlso on arrays4 min