Find a triplet that sum to a given target value

Common Interview Coding question and answer. Coding challenge is very frequent in big tech companies interview such as Amazon, Facebook or Google. Take a look at the Coding Challenge to – 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)

Read On Dglobaltech:

Quicksort Algorithm

Find Largest Smallest Numbers

We are solving three sum coding question using Javascript.

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