Skip to main content
DevHives

All Triplets That Sum to Zero

MediumArraysTwo pointersSorting253 tests

You get an integer array nums. Find every triplet of values [a, b, c] such that:

  • a, b and c come from three different positions in nums, and
  • a + b + c == 0.

Return each triplet only once, even if it can be built from more than one set of positions.

Order of the answer

  • Write each triplet in ascending order: a <= b <= c.
  • Sort the list of triplets in ascending order: first by a, then by b, then by c.
  • If there is no such triplet, return an empty list [].

Hint

Sort the array. Fix the first value, then find the other two with one pointer at each end of the rest. Skip a value when it is the same as the one before it, so no triplet is added twice. This takes O(n²) time, and the triplets come out already in the required order.

Examples

Example 1

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

These five triplets each add up to 0. Each is written in ascending order, and the list is sorted by the first value, then the second.

Example 2

Input:
[2,-1,2,-1,-4]
Output:
[[-4,2,2],[-1,-1,2]]

-4 + 2 + 2 = 0 uses the two different 2s. -1 + -1 + 2 = 0 can be built in more than one way, but it is listed once.

Example 3

Input:
[5,0,3,8]
Output:
[]

There is only one value that is not positive, so no three values can add up to 0.

Constraints

  • 0 <= nums.length <= 14
  • -10 <= nums[i] <= 10

Run checks your code against the 3 examples. Submit checks it against all 253 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.