Three Way to partition an Array

Given an array containing N integers, and an number S denoting a target sum.

Find all distinct integers that can add up to form target sum. The numbers in each triplet should be ordered in ascending order, and triplets should be ordered too.

Return empty array if no such triplet exists.

Note: For Simplicity we taking sum=0 always.

For exact problem visit Leetcode Link;

Sample Input Output

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [
  [-1, -1, 2],
  [-1, 0, 1],
]

Input: nums = []
Output: []

Input: [0, 0, 0, 0, 0]
Output: [0, 0, 0]

Solution Approach

There are many approach to solve this problem.

1. First: Generate all triplet and check if their sum is equal to sum.

   Time Complexity: O(N)

   Space Complexity: O(1)

   Where N is length of input array.

2. Second: For every element of array i check if there is a pair whose sum is sum-nums[i]. We can check pair sum in O(N) using hashing. Handling duplicate number will make this implementation complecated and also it will take O(N) extra space.

   Time Complexity: O(N*N)

   Space Complexity: O(N)

3. Third(Preferred for Above Problem): In this solution we will opimize the way we are searching Pair Sum by using sorting and Two Pointer approach.

   1. Sort the array TC: O(NlogN).
   2. Iterate from i=0 to n-1 and for every element of array i check if there is pair between i+1 to n-1 whose sum is sum - nums[i].
   3. If there any unique pair satisfy our condition will be pushed in ans array.
   4. For checking pair we used two pointer approach.

   Time Complexity: O(N*N)

   Space Complexity: O(1)

Javascript Implementation

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const ans = [] // to store all triplets
  nums.sort((a, b) => a - b) // Sorted array in ascending order

  function getPairs(i, j, n) {
    while (i < j) {
      if (nums[i] + nums[j] === n) {
        ans.push([-n, nums[i++], nums[j++]])
      } else if (nums[i] + nums[j] < n) {
        i++
      } else {
        j--
      }
      // To Avoid duplicate Triplets
      while (nums[i + 1] === nums[i]) {
        i++
      }
    }
  }

  for (let i = 0; i < nums.length - 2; i++) {
    // This if check will make sure we dont calculte triplet for same number
    if (i === 0 || nums[i] !== nums[i - 1]) {
      getPairs(i + 1, nums.length - 1, -nums[i])
    }
  }

  return ans
}