C++ Searching for the intersect of multiple arrays with different lengths in 0(n+m) complexity

Question

Currently I have multiple ordered arrays with varying length

int * arrs[5];
int arrs_length[5];
int arr0[] = {1, 5, 8};
int arr1[] = {1, 2, 3, 5, 7, 10, 11, 15};
int arr2[] = {1, 4, 5, 6};
int arr3[] = {1, 5, 9, 14, 16, 19};
int arr4[] = {1, 2, 4, 5, 6, 9, 9};
arrs[0] = arr0;
arrs_length[0] = sizeof(arr0) / sizeof(int);
arrs[1] = arr1;
arrs_length[1] = sizeof(arr1) / sizeof(int);
arrs[2] = arr2;
arrs_length[2] = sizeof(arr2) / sizeof(int);
arrs[3] = arr3;
arrs_length[3] = sizeof(arr3) / sizeof(int);
arrs[4] = arr4;
arrs_length[4] = sizeof(arr4) / sizeof(int);

I am trying to output the intersect of these arrays.

I start off by creating an unordered_map with the values from one of the arrays and use the count function to check if it exists. I run into problems when the 1 and 5 don't line up but it works if they do line up.

int intersect(int *arrs[], int arrs_length[], int *re_arr, int & re_size){
    unordered_map <int,int> myMap;
    int j=0;
    for (int i=0; i<arrs_length[0]; i++){
        myMap[arrs[0][i]];
    }

Can anyone give me an idea of how to search the unordered map properly and search multiple arrays at one time?

Answer 1

You can maintain an unordered map and do the following:

You can create an empty unordered set for each array. Then you can iterate over it and add +1 to the current element in the global map if its not in the current set and add it to the set. If it's already there, just ignore it.

After checking all the arrays, you should print such elements of the map that their value if equal to the number of arrays.

This solution is linear in the size of the input, so it has an optimal time complexity.