Example:

input:

array1 = [1,2,3,4]
array2 = [1,2]
array3 = [3]
array4 = [5,6]

output:

array4

input:

array1 = [1,2,3,4]
array2 = [1,2]
array3 = [3,5]
array4 = [5,6]

output:

None

How to design a solution in an efficient way(less time complexity)?

CodePudding user response：

This is one potential approach.

Time complexity: O(num_arrays * max_length_among_num_arrays)
Space complexity: O(sum_of_length_of_num_arrays)

const array1 = [1,2,3,4]
const array2 = [1,2]
const array3 = [3]
const array4 = [5,6]
const arrays = [array1, array2, array3, array4];

// Generate a mapping of: value -> number of arrays that have it
const map = new Map();
for (const arr of arrays) {
    const set = new Set(arr);
    for (const item of set) {
        if (!map.has(item)) {
            map.set(item, 0);
        }
        map.set(item, map.get(item)   1);
    }
}

// Find arrays for which all items have only appeared in one array
const res = [];
for (const arr of arrays) {
    let check = true;
    for (let i = 0; i < arr.length && check; i  ) {
        if (map.get(arr[i]) > 1) {
            check = false;
        }
    }
    if (check) {
        res.push(arr);
    }
}

console.log(res);