Array intersection Be A Ninja! Problem Description: In this problem you are given with two random integer arrays, you have to print their intersection. That is, you have to print all the elements that are present in both the given arrays, For example: If input is: Sizel of arr1-6 arrl[]= 268543 Size? of arr2= 4 anr2(}=2347 Output: Elements present in both the arrays: 2 3 4 How to approach? Approach 1: The first approach we can think is that we can run 2 loops. In the outer loop pick one element of array 1 and then with the help of an inner loop check whether the same element exists in array 2 or not. Ifthe same element is found then, we found an intersection so we print it, and to handle the case of duplicates, we can replace this element with minus infinity. Pscudo C r this approach Function intersection. For i= 0 to iless than sizel For j = 0 to j less than size2: Marr] fi] equal to arr2{j]: Print(arr2{j)) arr2[j]=minus infinity break ‘Time Complexity for this approach: Time complexity for this approach is O(sizel + size2), which is not good, hence, we are moving to the next approach. Approach 2: A better solution for this problem is to sort both the arrays. Now, we have to find the intersection of 2 sorted arrays: 1) Use two index variables i and j, initialize them as i2) If arr [i] is smaller than arr2[j] then increment i. 3) If arrl[i] is greater than arr2{j] then increment j. 4) [fboth are same then print any of them and increment both i and j. Time Complexity for this approach: Time complexity for sorting both arrays will be O(sizel *log(sizel) + size2*log(size2)) and then finding the interscetion will have a time complexity of O(sizel+size2). Let us dry run the code for: Sizel of al = 6 arrl[]=268543 Size2 of an2=4 arr2[]=2347 Let the input arrays be arr and arr2 We will sort both the arrays. Let the pointer to the arr and arr? be i and j, respectively, Initially, i in j are pointing to 0" index of arr1 and arr2, respectively. a i bo no i‘We will compare element at i (represented by black arrow) and j (represented by red arrow). Initially, i and j are pointing to smallest elements of the arrays. We will move the pointer, which is pointing to smaller element because we want to print their intersection and next intersection can only be found by moving pointer pointing to smaller element. In this case, since elements pointed are equal, so, we will print the element in console and move both pointers. Console: 2 4. ‘We will again compare element at i and j. In this case, as well, since elements pointed are equal, so, \we will print the element in console and move both pointers. a a a a Console: 23 5, ‘We will again compare element at i and j. In this case, as well, since elements pointed are equal, so, ill print the element in console and move both pointers. ie Console: 2346. ‘We will again compare element at i and j. In this case, since elements pointed by iis smaller than that pointed by j, so, we will move ith pointer. Console: 234 7. ‘We will again compare element at i and j. In this case, since elements pointed by iis smaller than that pointed by j, so, we will move ith pointer. Console: 234 8. ‘We will again compare element at i and j. In this case, since elements pointed by is smaller than that pointed by i, so, we will move jth pointer. Console: 2349, We can’t compare the elements now, as we have reached the end of second array. We can terminate the algorithm now, as no more intersections can be found now. a a Fo Console: 234 Approach 3: The best solution here is to use hashmaps to further reduce the time complexity of this problem, To continue with the hashmaps we can proceed with the following steps: 1. Initialize an empty hashmap mapp. 2. Iterate through the first array, and put every element of this array in the mapp with its corresponding count. 3. Now for every element of the second array, search it in the hashmap and if it is present then print it and decrement its corresponding count, After decrement, if the corresponding count becomes zero, then we should remove the element from the mapp. ‘Time Complexity for this approach: Time complexity for this approach is O(m+n) as searching and inserting operations in hashmaps are performed in O(1) time. Function intersection: Create an empty hashmap mapp For i=0 to i less than sizel. Increment the count of each element of this array in hashmap For i=0 to i less than size2: Many element of array? exists in hashmap: Print(element) Decrement the count of that element in hashmap. Uf count corresponding to that element is zero Delete(element, mapp)Q Let us dry run the code for: Sizel of arrl = 6 arrl[]=268543 Size2 of arr2 = 4 an2{]=2347 Creating Inserting each element mapp Empty mapp an empty hashmap ORBAN yt \t of array! with its count in the hashmap mapp 2+0 6-1 B+ 5-1 4d 3-41 Going through each element of array2, here the first element is 2 and since 2 exists in hashmap so, print it and then decrement its count from the mapp and now move to the next element,Now, the second element 3 exists in hashmap so print it and then decrement its count from the mapp and now move to the next element. mapp 2+ 6 Be oe rs 34 eosaso The third element, 4 exists in hashmap so print it and then decrement its count from the mapp and now move to the next element. ‘Now, when we move to 7, it does not exist in the hashmap, so, we do nothing Our final output will be: 2 3 4