{"post":"

Input: arr1[] = [7, 1, 5, 2, 3, 6] , arr2[] = [3, 8, 6, 20, 7]

Output: [3, 6, 7]

# Brute Force

Pseudo Code:

Initialize intersection array as empty.
Do following for every element x of the first array.
\na. If x is present in second array, then copy x to I.
\nb. Return Intersection.

Code:

#include <iostream>\n#include <algorithm>\nusing namespace std;\nvoid intersection(int arr1[], int arr2[], int n1, int n2)\n{\n\tint i, j;\n\tfor (i = 0; i < n1; i++)\n\t{\n\t\tfor (j = 0; j < n2; j++)\n\t\t{\n\t\t\tif (arr1[i] == arr2[j])\n\t\t\t{\n\t\t\t\tcout << arr1[i] << \" \";\n\t\t\t}\n\t\t}\n\t}\n}\nint main()\n{\n\tint arr1[] = { 3, 11, 5, 22, 42, 476, 866, 34, 23, 78, 23, 8 };\n\tint arr2[] = { 3, 11, 6, 866, 34 };\n\tint m = sizeof(arr1) / sizeof(arr1[0]);\n\tint n = sizeof(arr2) / sizeof(arr2[0]);\n\tcout << \"Intersection of two arrays is n\";\n\tintersection(arr1, arr2, m, n);\n\treturn 0;\n}

Space complexity : O(1)
\nTime complexity : O(n1*n2), where n1 is the no. of elements of the first array and n2 is no. of elements of the second array.

# Optimized Approach

Pseudo Code:

Initialize intersection I as empty.
Find smaller of m and n and sort the smaller array.
For every element x of larger array, do following
\na. Binary Search x in smaller array. If x is present, then copy it to I.
\nb. Return I.

Code:

#include <iostream>\n#include <algorithm>\nusing namespace std;\nint binarySearch(int arr[], int l, int r, int x);\nvoid printIntersection(int arr1[], int arr2[], int m, int n)\n{\nif (m > n)\n{\nint *tempp = arr1;\narr1 = arr2;\narr2 = tempp;
\n\tint temp = m;\n\tm = n;\n\tn = temp;\n}\nsort(arr1, arr1 + m);\nfor (int i = 0; i &lt; n; i++)\n\tif (binarySearch(arr1, 0, m - 1, arr2[i]) != -1)\n\t\tcout &lt;&lt; arr2[i] &lt;&lt; \" \";\n
\n}\nint binarySearch(int arr[], int l, int r, int x)\n{\nif (r >= l)\n{\nint mid = l + (r - l) / 2;\nif (arr[mid] == x) return mid;\nif (arr[mid] > x)\nreturn binarySearch(arr, l, mid - 1, x);
\n\treturn binarySearch(arr, mid + 1, r, x);\n}\nreturn -1;\n
\n}\nint main()\n{\nint arr1[] = { 3, 11, 5, 22, 42, 476, 866, 34, 23, 78, 23, 8 };\nint arr2[] = { 3, 11, 6, 866, 34 };\nint m = sizeof(arr1) / sizeof(arr1[0]);\nint n = sizeof(arr2) / sizeof(arr2[0]);\ncout << \"Intersection of two arrays is n\";\nprintIntersection(arr1, arr2, m, n);\nreturn 0;\n}

Output:

Intersection of two arrays is n 3, 11, 866, 34

This is how we solve the problem of Intersection of two arrays.

\n","title":"Intersection Of Two Arrays Problem","authorDetails":{"name":"Anshuman Raina","slug":"anshuman-raina"},"description":"Program to find Intersection Of Two Arrays in C++ with time complexity and space complexity analysis,","slug":"intersection-of-two-arrays-problem/","articleId":"636a83447bb1ce5072622b8f","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}