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.

Example 1:

Input: [-3, -3, -1, 0, 3, 4]
Output: [[-3, -1, 4], [-3, 0, 3]]

Example 2:

Input: [5, -2, -3]
Output: [[-3, -2, 5]]

Example 3:

Input: [1, 2, 3]
Output: []

Constraints:

• 3 <= nums.length <= 10^3
• -1000 <= nums[i] <= 1000

Solution Breakdown

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 [-3, -3, -1, 0, 3, 4] sorting gives [-3, -3, -1, 0, 3, 4]; anchoring at the first -3 finds [-3, -1, 4] and [-3, 0, 3], and the second -3 is skipped.

Edge cases: the outer dedupe skip prevents repeated anchors (e.g. the two -3s); [5, -2, -3] yields a single triplet because the anchors and inner values are all distinct; 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.