« Find array intersection

Problem

You have been given two integer arrays/list(ARR1 and ARR2) of size N and M, respectively. You need to print their intersection; An intersection for this problem can be defined when both the arrays/lists contain a particular value or to put it in other words, when there is a common value that exists in both the arrays/lists.

Note :

Input arrays/lists can contain duplicate elements.

The intersection elements printed would be in the order they appear in the first sorted array/list(ARR1).

Input format :

The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the first array/list.

The second line contains 'N' single space separated integers representing the elements of the first the array/list.

The third line contains an integer 'M' representing the size of the second array/list.

The fourth line contains 'M' single space separated integers representing the elements of the second array/list.

Output format :

For each test case, print the intersection elements in a row, separated by a single space.

Output for every test case will be printed in a separate line.

Constraints :

1 <= t <= 10^2

0 <= N <= 10^6

0 <= M <= 10^6

Time Limit: 1 sec

Sample Input 1 :

2

6

2 6 8 5 4 3

4

2 3 4 7

2

10 10

1

10

Sample Output 1 :

2 3 4

10

Sample Input 2 :

1

4

2 6 1 2

5

1 2 3 4 2

Sample Output 2 :

1 2 2

Explanation for Sample Output 2 :

Since, both input arrays have two '2's, the intersection of the arrays also have two '2's. The first '2' of first array matches with the first '2' of the second array. Similarly, the second '2' of the first array matches with the second '2' if the second array.

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14void intersection(int *arr1, int *arr2, int n, int m)
15{
16    int *p = 0;
17    if (n < m)
18    {
19        p = new int[n];
20    }
21    else
22    {
23        p = new int[m];
24    }
25
26    unordered_map<int, int> umap2;
27    for (int i = 0; i < m; i++)
28    {
29        if (umap2.find(arr2[i]) != umap2.end())
30        {
31            umap2[arr2[i]] = umap2[arr2[i]] + 1;
32        }
33        else
34        {
35            umap2[arr2[i]] = 1;
36        }
37    }
38
39    sort(arr1, arr1 + n);
40
41    for (int i = 0; i < n; i++)
42    {
43        if (umap2.find(arr1[i]) != umap2.end() && umap2[arr1[i]] > 0)
44        {
45            cout << arr1[i] << " ";
46        }
47        umap2[arr1[i]] = umap2[arr1[i]] - 1;
48    }
49
50    cout << endl;
51}
52
53int main()
54{
55    int t;
56    cin >> t;
57    while (t > 0)
58    {
59
60        int size1, size2;
61
62        cin >> size1;
63        int *input1 = new int[size1];
64
65        for (int i = 0; i < size1; i++)
66        {
67            cin >> input1[i];
68        }
69
70        cin >> size2;
71        int *input2 = new int[size2];
72
73        for (int i = 0; i < size2; i++)
74        {
75            cin >> input2[i];
76        }
77
78        intersection(input1, input2, size1, size2);
79
80        delete[] input1;
81        delete[] input2;
82
83        cout << endl;
84        t--;
85    }
86
87    return 0;
88}