Problem
Given a list of numbers, find all the unique quadruples that sum up to a given target value.
Example
{
"arr": [0, 0, 1, 3, 2, -1],
"target": 3
}
Output:
[
[-1, 0, 1, 3],
[0, 0, 1, 2]
]
Solution
const removeDuplicates = (arr = []) => {
const map = new Map();
arr.forEach((x) => map.set(JSON.stringify(x), x));
arr = [...map.values()];
return arr;
};
function findFourElements(arr, target) {
// Store sums of all pairs in a hash table
arr.sort();
let n = arr.length;
let result = [];
let mp = new Map();
for (let i = 0; i < n - 1; i++)
for (let j = i + 1; j < n; j++)
mp.set(arr[i] + arr[j], [i, j]);
// Traverse through all pairs and search
// for target - (current pair sum).
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
let sum = arr[i] + arr[j];
// If target - sum is present in hash table,
if (mp.has(target - sum)) {
// Making sure that all elements are
// distinct array elements and an
// element is not considered more than
// once.
let p = mp.get(target - sum);
if (p[0] != i && p[0] != j
&& p[1] != i && p[1] != j) {
let matchedResult = [
arr[i],
arr[j],
arr[p[0]],
arr[p[1]]];
matchedResult.sort();
result.push(matchedResult);
break;
}
}
}
}
let finalRes = removeDuplicates(result);
console.log(finalRes);
}
// Problem
let arr = [0, 0, 1, 3, 2, -1];
let target = 3;
// Function call
findFourElements(arr, target);
Time and Space Complexity
Time Complexity : O(n^4)
Space Complexity: O(n^4)