Tarandeep singh

Intersection of Two Arrays

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.

Author