Intersection Of Two Arrays
Given two arrays Arr1[] and Arr2[] of length n and m, respectively. The task is to find the intersection of elements of Arr1 and Arr2. The intersection is the list of common and distinct elements between Arr1 and Arr2. The intersection list can be in any order.
Example
Input:
Arr1 = [1, 2, 3, 4, 5, 6]
Arr2 = [1, 2, 3, 4, 5]
Output:
[1, 2, 3, 4, 5]
Explanation: Common elements between Arr1 and Arr2 is 1, 2, 3, 4, 5. So, [1, 2, 3, 4, 5] is the output.
Input:
Arr1 = [1, 2, 4]
Arr2 = [5, 6, 7]
Output:
[]
Explanation: There is no common value between Arr1 and Arr2. So, an empty list will be returned and printed.
Constraints
1<=Arr1.length,Arr2.length<=1000
0<=Arr1[i],Arr2[i]<=1000
Method 0: Using Set
We can find the intersection of two Arrays using the below algorithm:
- initialize an empty set.
- Iterate on Arr1 and add every element in the Set.
- For every element in Arr2, check:
- If the element is present in the Set, then print the element.
C++ Implementation
void intersection(int Arr1[], int m, int Arr2[], int n)
{
// Defining a Set
set<int> Set;
// Adding Arr1 values to Set
for (int i = 0; i < m; i++)
Set.insert(Arr1[i]);
// check if Arr2's value is present in Set
for (int i = 0; i < n; i++){
if (Set.find(Arr2[i]) != Set.end()){
// If value is present in Set, print it
cout << Arr2[i] << " ";
}
}
}
Java Implementation
static void intersection(int Arr1[], int m, int Arr2[], int n)
{
// Defining a Set
HashSet<Integer> Set = new HashSet<>();
// Adding Arr1 values to Set
for (int i = 0; i < m; i++)
Set.add(Arr1[i]);
// check if Arr2's value is present in Set
for (int i = 0; i < n; i++)
// If value is present in Set, print it
if (Set.contains(Arr2[i])){
System.out.print(Arr2[i] + " ");
}
}
Python Implementation
def intersection(Arr1, Arr2, m, n):
# Defining set
Set = set()
# Add all elements of Arr1 in set
for i in Arr1:
Set.add(i)
# For each value of Arr2, check it in Set
for i in Arr2:
if i in Set:
# Print the common element
print(i, end=" ")
Complexity Analysis
Time Complexity: O(M* log(M)+N) => Both the arrays will be traversed with length M and N, inserting an element in a set takes logarithmic time i.e. O(log(M)). So, total complexity is O(M * log(M)+N). Space Complexity: O(N) => N space will be needed for storing all values of Arr1.
Method 1: Using Map Data Structure
In this approach, we will be using map data structure for finding the intersection between the Arrays.
- initialize an empty map or dictionary.
- Iterate on Arr1 and add every element as a key in the map.
- For every element in Arr2, check:
- If the element is present in the map as a key, then print the element.
C++ Implementation
void intersection(int Arr1[], int Arr2[], int m, int n)
{
// Defining a map
map<int, int> mp;
// Adding Arr1 values to map
for (int i = 0; i < m; i++)
mp[Arr1[i]] = i;
// check if Arr2's value is present in map
for (int i = 0; i < n; i++){
if (mp.find(Arr2[i]) != mp.end()){
// If value is present in map, print it
cout << Arr2[i] << " ";
}
}
}
Java Implementation
static void intersection(int Arr1[], int m, int Arr2[], int n)
{
// Defining a map
Map<Integer, Integer> mp = new HashMap<Integer, Integer>();
// Adding Arr1 values to map
for (int i = 0; i < m; i++)
mp.put(Arr1[i], i);
// check if Arr2's value is present in map
for (int i = 0; i < n; i++)
// If value is present in map, print it
if (mp.containsValue(Arr2[i])){
System.out.print(Arr2[i] + " ");
}
}
Python Implementation
def intersection(Arr1, Arr2, m, n):
# Defining set
mp = {}
# Add all elements of Arr1 in map
for i in Arr1:
mp[i]=i
# For each value of Arr2, check it in map
for i in Arr2:
if i in mp:
# Print the common element
print(i, end=" ")
Complexity Analysis
Time Complexity: O(M+N) => We are traversing both the arrays one by one. First storing all the values of Arr1 in the map and then checking that the values of Arr2 are present in the map or not. Space Complexity: O(N) => N space for storing all the distinct elements of both the arrays in the map.
Method 2: Naive
We can use a naive approach where we are not worrying about time complexity and are making a simple code where the work is done.
Intersection:
For finding intersection of both the arrays the naive approach will be:
- initialize an empty intersection array.
- for each element in Arr1, check whether the element is present Arr2
- If the element is present in the Arr2, and the element is also not in the intersection array, push that element in the intersection array.
- Else, do nothing.
- Finally, print all the elements in the union array.
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
void intersection(int arr1[], int arr2[], int m, int n){
// Defining variables
set<int> x, y, ans;
// Inserting values in the set
for(int i = 0; i < m; i++){
x.insert(arr1[i]);
}
for(int i = 0; i < n; i++){
y.insert(arr2[i]);
}
// Checking if the value is present in other collection or not
for(auto i: x){
if(y.count(i)){
if(!ans.count(i))
ans.insert(i);
}
}
// Printing the ans array
for(auto i: ans) cout << i << " ";
}
// Driver code
int main(){
int arr1[5] = {1, 2, 3, 3, 4};
int arr2[5] = {3, 4, 5, 6, 7};
intersection(arr1, arr2, 5, 5);
return 0;
}
Java Implementation
import java.util.*;
import java.lang.*;
import java.io.*;
class Code
{
static void intersection(ArrayList<Integer>Arr1, ArrayList<Integer>Arr2)
{
ArrayList<Integer> inter = new ArrayList<Integer>();
for(int i:Arr1){
// Checking if the value is present in other collection or not
if(Arr2.contains(i)){
if(inter.contains(i)){
continue;
}
else{
inter.add(i);
}
}
}
for(int i:inter){
// Printing the ans array
System.out.print(i+" ");
}
}
// Driver code
public static void main (String[] args)
{
ArrayList<Integer> Arr1 = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 3, 4));
ArrayList<Integer> Arr2 = new ArrayList<Integer>(Arrays.asList(3, 4, 5, 6, 7));
intersection(Arr1,Arr2);
}
}
Python Implementation
def intersection(Arr1, Arr2):
# Defining the answer array
inter = []
# Checking for each value
for i in Arr1:
if i in Arr2:
if i not in inter:
inter.append(i)
# Printing the intersection array
for i in inter:
print(i, end=' ')
# Driver Code
Arr1 = [1, 2, 3, 3, 4]
Arr2 = [3, 4, 5, 6, 7]
intersection(Arr1, Arr2)
Output:
3 4
Complexity Analysis
Time Complexity: O(M*N) => For every element in Arr2 we are checking its presence in the Arr1 array and then in intersection array. Space Complexity: O(min(M,N)) => min(M,N) space for storing all the distinct elements of both the arrays in an intersection array.
Method 3: Using Sorting
We can sort both the arrays and then will apply the below algorithm:
- initialize two index variables, i and j with 0.
- If Arr1[i]<Arr2[j], increment i.
- If Arr1[i]>Arr2[j], increment j.
- Else, it means both the values are same, print those values.
C++ Implementation
void intersection(int Arr1[], int m, int Arr2[], int n)
{
// Sorting the arrays
sort(Arr1, Arr1 + m);
sort(Arr2, Arr2 + n);
int i = 0, j = 0;
while (i < m && j < n) {
// If value is less than Arr2 value i++
if (Arr1[i] < Arr2[j])
i+=1;
// If Arr2 value is less than Arr1 value j++
else if (Arr2[j] < Arr1[i])
j+=1;
else
{
// Print the common element
cout << Arr2[j] << " ";
i+=1;
j+=1;
}
}
Java Implementation
static void intersection(int Arr1[], int m, int Arr2[], int n)
{
// Sorting the arrays
Arrays.sort(Arr1);
Arrays.sort(Arr2);
int i = 0, j = 0;
while (i < m && j < n) {
// If value is less than Arr2 value i++
if (Arr1[i] < Arr2[j])
i+=1;
// If Arr2 value is less than Arr1 value j++
else if (Arr2[j] < Arr1[i])
j+=1;
else
{
// Print the common element
System.out.print(Arr2[j] + " ");
i+=1;
j+=1;
}
}
}
Python Implementation
def intersection(Arr1, Arr2):
# Sorting the arrays
Arr1.sort()
Arr2.sort()
i=0
j=0
while(i<len(Arr1) and j<len(Arr2)):
# If value is less than Arr2 value i+=1
if(Arr1[i]<Arr2[j]):
i+=1
# If Arr2 value is less than Arr1 value j++
elif(Arr1[i]>Arr2[j]):
j+=1
else:
# Print the common element
print(Arr1[i], end=' ')
i+=1
j+=1
Complexity Analysis
Time Complexity: O(N*logN + M*logM) => both the arrays will be sorted and then will be traversed. Space Complexity: O(1) => No space is needed to store the intersection values.
Method 4: Kind Of Hashing Technique Without Using Any Predefined Collections
In this approach, we are using the hashing technique with the help of other array. The values of both the arrays will be mapped to the appropriate position in the other array.
We can find the intersection of two Arrays using this approach with the help of below algorithm:
- Initialize the Ans array with size m + n
- Iterate over Arr1 and find the appropriate index for the elements of Arr1 to be mapped in the Ans array.
- Repeat the process for Arr2 elements but check if a collision is happening during hashing. If collision occurs, simply print the value as it is a repeated value.
C++ Implementation
#include<bits/stdc++.h>
using namespace std;
void intersection(int a[], int b[], int m, int n){
// Initialize ans array
int v = (m+n);
int ans[v]={0};
// Perform hashing of Arr1 values in ans array
for (int i = 0; i < m; i++){
if (a[i] != 0) {
int p = a[i] % v;
p = p % v;
if (ans[p] == 0)
ans[p] = a[i];
}
}
// Perform hashing of Arr2 values in ans array
for (int i = 0; i < n; i++){
if (b[i] != 0) {
int p = b[i] % v;
p = p % v;
if (ans[p] == 0)
ans[p] = b[i];
else {
// If collision occurs, print the array value
if (ans[p] == b[i])
cout<<b[i]<<" ";
}
}
}
}
// Driver code
int main(){
int arr1[5] = {1, 2, 3, 4, 5};
int arr2[3] = {2, 3, 4};
intersection(arr1, arr2, 5, 3);
return 0;
}
Java Implementation
import java.util.*;
import java.lang.*;
import java.io.*;
class Main{
static void intersection(int[] a, int[] b)
{
// Initialize ans array
int v = (a.length + b.length);
int ans[] = new int[v];
// Perform hashing of Arr1 values in ans array
for (int i = 0; i < a.length; i++){
if (a[i] != 0) {
int p = a[i] % v;
p = p % v;
if (ans[p] == 0){
ans[p] = a[i];
}
}
}
// Perform hashing of Arr2 values in ans array
for (int i = 0; i < b.length; i++){
if (b[i] != 0) {
int p = b[i] % v;
p = p % v;
if (ans[p] == 0)
ans[p] = b[i];
else {
// If collision occurs, print the array value
if (ans[p] == b[i])
System.out.print(b[i] + " ");
}
}
}
}
// Driver code
public static void main (String[] args)
{
int Arr1[] = {1, 2, 3, 4, 5};
int Arr2[] = {2, 3, 4};
intersection(Arr1,Arr2);
}
}
Python Implementation
def intersection(Arr1, Arr2):
# Initialize the ans array
v = len(Arr1) + len(Arr2)
ans = [0]*v
# Perform hashing of Arr1 values in ans array
for i in range(len(Arr1)):
if (Arr1[i] != 0):
p = Arr1[i] % v
p = p % v
if (ans[p] == 0):
ans[p] = Arr1[i]
# Perform hashing of Arr2 values in ans array
for i in range(len(Arr2)):
if (Arr2[i] != 0):
p = Arr2[i] % v
p = p % v
if (ans[p] == 0):
ans[p] = Arr2[i]
else:
# If collision occurs, print the array value
if (ans[p] == Arr2[i]):
print(Arr2[i],end=" ")
arr1 = [1, 2, 3, 4, 5]
arr2 = [2, 3, 4]
intersection(arr2, arr1)
Output:
2 3 4
Complexity Analysis
Time Complexity: O(M+N) => Both the Arrays will be traversed for hashing. Space Complexity: O(M+N) => An extra array of size N+M is required to store the hashed values.
Conclusion
- The problem statement here is to find the intersection of elements of Arr1 and Arr2.
- Intersection is the list of common and distinct elements between Arr1 and Arr2. The intersection list can be in any order.
- There are many techniques to solve this problem:
- Using Set
- Using map data structure
- Naive Approach
- Using Sorting
- Kind of hashing technique without using any predefined Collections
- Every Approach has different time complexity and space complexity depending on the data structure used. So, each approach can be efficient at different situations.
