Find all triplets with sum zero in a given array

Problem Statement

Given an array of unsorted numbers, find all unique triplets in it that add up to zero.

Example 1:

Input: [-3, 0, 1, 2, –1, 1, –2]
Output: [-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]
Explanation: There are four unique triplets whose sum is equal to zero.

Example 2:

Input: [-5, 2, –1, –2, 3]
Output: [[-5, 2, 3], [-2, –1, 3]]
Explanation: There are two unique triplets whose sum is equal to zero.

Solution

This problem follows the Two Pointers pattern and shares similarities with Pair with Target Sum. A couple of differences are that the input array is not sorted and instead of a pair we need to find triplets with a target sum of zero.
To follow a similar approach, first, we will sort the array and then iterate through it taking one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ and ‘Z’ such that X + Y + Z =0. At this stage, our problem translates into finding a pair whose sum is equal to “−X” (as from the above equation Y + Z == -X).
Another difference from Pair with Target Sum is that we need to find all the unique triplets. To handle this, we have to skip any duplicate number. Since we will be sorting the array, so all the duplicate numbers will be next to each other and are easier to skip.

Below is the code written in Javascript:

/**

• @param {number[]} nums

• @return {number[][]}
  */
  function tripletSum(nums) {
  nums.sort((a,b)=>a-b);
  let triplets = [];

  for (var i = 0; i < nums.length; i++) {
  if (i > 0 && nums[i] === nums[i-1]) { // skip duplicate elements
  continue;
  }
  // for each nums[i] or element, search pair such that their sum equals -nums[i]
  search_pair(nums, -nums[i], i+1, triplets)
  }
  return triplets;
  };

function search_pair(arr, target_sum, index, triplets) {
let low = index, high = arr.length - 1;

while (low < high) {
    if (arr[low] + arr[high] === target_sum) {
        triplets.push([-target_sum, arr[low], arr[high]]);
        low++;
        high--;
    
        while (low < high && arr[low] === arr[low-1]) low++;
    
        while (low < high && arr[high] === arr[high+1]) high--;     
        
    } else if (target_sum > arr[low] + arr[high]) {
        low++;
    } else {
        high--;
    }    
} 

}

document.write(tripletSum([-3, 0, 1, 2, -1, 1, -2])+'
');
document.write(tripletSum([-5, 2, -1, -2, 3])+'
');
document.write(tripletSum([-1, 0, 1, 2, -1, -4])+'
');

Time complexity

Sorting the array will take O(N * logN). The search_pair() function will take O(N).
As we are calling search_pair() for every number in the input array, this means that overall tripletSum() will take O(N * logN + N^2), which is asymptotically equivalent to O(N^2).

Space complexity

Ignoring the space required for the output array, the space complexity of the above algorithm will be O(N) which is required for sorting.

This article was originally published on Golibrary (https://www.golibrary.co/find-all-triplets-with-sum-zero-in-an-array/)