3Sum
The problem
Return every distinct triplet of values in an integer array that sums to zero. A triplet uses three different indices; duplicate value-triplets should appear once.
Example
[-2, 0, 2, 2, -1, -1] → [[-2, 0, 2], [-1, -1, 2]]
Need a hint?
Fix one value, then solve a sorted two-sum problem.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Sort the array. For each first position, skip repeated first values, then move left and right pointers through the suffix. Increase left when the sum is too small and decrease right when it is too large. After a match, move both and skip duplicate endpoint values.
Complexity
O(n²) time; sorting space depends on the implementation, plus the result.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.