Coding Challenge – Three Sum Target. Find a triplet that sum to a given target value

Question: Find a triplet that sum to a given target value.

For Example: here is the given array and target is 10. We need to figure out which three number sums up to the 10.

const arr = [2,3,4,-3,-4,5,8,15,10,6,7];
let target = 10;

The Answer to the question is => (2,3,5), (-3,5,8)

A simple solution to the problem is to generate all possible triplets and compare the sum of those three numbers to given target value.

We can achieve this by using three for loops.

So it would be something like this — (2,3,4), (2,3,-3),(2,3,-4), (2,3,5) and so on.

then we will check 2+3+4 === 10 ? or not.

Nice solution but it creates unnecessary repeated work and also think about very large number of data, three loops is very expensive.

Instead we can store sum so we don’t have to create already identical pairs again and again. Yes, we can use Hashmap!

Here is the efficient solution with  O(n^2) Time Complexity!

/**
* given an integer array, find the number of triplets that have sum more than a particular value.
*/
function triplateSum(arr, target) {
  let results = [];
  for (let i = 0; i < arr.length; i++) {
    let finalT = target - arr[i];
    let map = {};
    for (let j = i+1; j < arr.length; j++) {
      if (map[arr[j]]) {
        results.push([arr[j], arr[i], map[arr[j]]]);
      }
      else {
        map[finalT-arr[j]] = arr[j];
      }
    }
  }
  return results;
}
console.log(triplateSum(arr, target));