3Sum

Problem

Fraud detection systems flag unusual transaction clusters - for example, three charges that perfectly cancel each other out, suggesting a round-trip scheme. Given an integer array, return all unique triplets that sum to zero. The result must not contain duplicate triplets.

Input: [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]
Input: [0, 0, 0]             → [[0, 0, 0]]
Input: [0, 1, 1]             → []

Solution

Approach: sort, then fix one element and run opposite-ends two pointers on the rest.

Sorting first turns the cubic brute force into an O(n²) scan and makes deduplication a matter of skipping equal neighbors. The outer loop fixes nums[index] as the first element of the triplet; the inner two-pointer search over index+1 .. n-1 looks for a pair summing to -nums[index]. On the sorted subarray, if total < 0 the sum is too small so left moves up to a larger value, and if total > 0 it is too large so right moves down - the same monotonic argument that powers two-sum on a sorted array. When total == 0 a triplet is recorded.

Deduplication happens at two levels. The outer if index > 0 and nums[index] == nums[index-1]: continue skips a fixed value already used as an anchor. After recording a hit, the two inner while loops slide left and right past any repeats of the just-used values before the final left += 1 / right -= 1, so the same triplet is never emitted twice. On [-1, 0, 1, 2, -1, -4] sorting gives [-4, -1, -1, 0, 1, 2]; anchoring at the first -1 finds [-1, -1, 2] and [-1, 0, 1], and the second -1 is skipped.

Edge cases: the outer dedupe skip prevents repeated anchors (e.g. the two -1s); [0, 0, 0] yields a single [0, 0, 0] because the inner skips collapse the extra zeros; arrays with no zero-sum triplet return an empty list.

Complexity: O(n²) time, O(1) extra space (ignoring the output) - the sort is O(n log n) and each anchor drives a linear two-pointer pass.