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

Output: [3, 6, 7]

# Brute Force

Pseudo Code:

  1. Initialize intersection array as empty.
  2. Do following for every element x of the first array.
    a. If x is present in second array, then copy x to I.
    b. Return Intersection.

Code:

#include <iostream>
#include <algorithm>
using namespace std;
void intersection(int arr1[], int arr2[], int n1, int n2)
{
	int i, j;
	for (i = 0; i < n1; i++)
	{
		for (j = 0; j < n2; j++)
		{
			if (arr1[i] == arr2[j])
			{
				cout << arr1[i] << " ";
			}
		}
	}
}
int main()
{
	int arr1[] = { 3, 11, 5, 22, 42, 476, 866, 34, 23, 78, 23, 8 };
	int arr2[] = { 3, 11, 6, 866, 34 };
	int m = sizeof(arr1) / sizeof(arr1[0]);
	int n = sizeof(arr2) / sizeof(arr2[0]);
	cout << "Intersection of two arrays is n";
	intersection(arr1, arr2, m, n);
	return 0;
}

Space complexity : O(1)
Time 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:

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

Code:

#include <iostream>
#include <algorithm>
using namespace std;

int binarySearch(int arr[], int l, int r, int x);
void printIntersection(int arr1[], int arr2[], int m, int n)
{
	if (m > n)
	{
		int *tempp = arr1;
		arr1 = arr2;
		arr2 = tempp;

		int temp = m;
		m = n;
		n = temp;
	}
	sort(arr1, arr1 + m);
	for (int i = 0; i < n; i++)
		if (binarySearch(arr1, 0, m - 1, arr2[i]) != -1)
			cout << arr2[i] << " ";
}
int binarySearch(int arr[], int l, int r, int x)
{
	if (r >= l)
	{
		int mid = l + (r - l) / 2;
		if (arr[mid] == x) return mid;
		if (arr[mid] > x)
			return binarySearch(arr, l, mid - 1, x);

		return binarySearch(arr, mid + 1, r, x);
	}
	return -1;
}
int main()
{
	int arr1[] = { 3, 11, 5, 22, 42, 476, 866, 34, 23, 78, 23, 8 };
	int arr2[] = { 3, 11, 6, 866, 34 };
	int m = sizeof(arr1) / sizeof(arr1[0]);
	int n = sizeof(arr2) / sizeof(arr2[0]);
	cout << "Intersection of two arrays is n";
	printIntersection(arr1, arr2, m, n);
	return 0;
}

Output:

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

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

Report Error/ Suggestion

Related Posts:

[yuzo_views]











CopyRight © 2020

CopyRight © 2020