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