Javascript Solution `Triplet Sum` Problem

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 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 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.

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;
};