Pair on a sorted array

Before you start

• Sorting

  3Sum sorts first. Sorting is taught in the Search course. Here you only need to know it costs O(n log n).

  Open lesson

Why it matters

Finding combinations that balance to zero appears in reconciliation and is a common test of duplicate handling. Trying every triple becomes unusable even for a few thousand values, and repeated values can produce the same answer many times. For [-1, 0, 1, 2, -1, -4], return each distinct zero-sum triple once without cubic enumeration.

Return every unique triplet (nums[i], nums[j], nums[k]) with i < j < k that sums to 0. Sort each triplet ascending, then sort the list of triplets.

Input

nums = [-1, 0, 1, 2, -1, -4]

Output

[[-1, -1, 2], [-1, 0, 1]]

After sorting to [-4, -1, -1, 0, 1, 2], fix -1 and seek a pair totaling 1; -1 + 2 and 0 + 1 give the two answers. One ordered pair scan per first value replaces brute force's O(n³) triple checks.

Sort the example into [-4, -1, -1, 0, 1, 2]. Fix one value at i, then place left after it and right at the end. With i on the first -1, the total -1 + -1 + 2 is 0, so record [-1, -1, 2].

Move both ends inward to 0 and 1, which gives [-1, 0, 1]. A negative total needs a larger left value; a positive total needs a smaller right value. When i reaches the second -1, skip it because that starting value has already produced every possible triple.