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:

Output:

Explanation: Common elements between Arr1 and Arr2 is 1, 2, 3, 4, 5. So, [1, 2, 3, 4, 5] is the output.

Input:

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

Java Implementation

Python Implementation

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

Java Implementation

Python Implementation

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

Java Implementation

Python Implementation

Output:

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

Java Implementation

Python Implementation

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

Java Implementation

Python Implementation

Output:

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.