Sorting Problem

4 Sum

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)

Leave a comment