How do you find the intersection and union of two arrays?
To get growth in your career, keeping up with the latest languages and concepts is quite important, especially when you are a programmer.
Therefore, one should always practice coding questions to keep themselves updated with the latest interview or exam trends.
If you are also looking for some latest interview questions, we have come up with one common question which is generally asked. Here, we are going to talk about how to find the union and the intersection of two arrays and all the methods that you can use to find the union and intersection.
However, if you are not familiar with what a union or an intersection is, let’s understand that first!
What is the Union Of Two Arrays?
The union of an array is an array that contains all the elements present in one of the arrays. In case one element is present in both arrays, we will add that element only once in the union array.
Let’s consider the following example to understand better:
Array 1: { 1, 2, 3, 4, 5, 10}
Array 2: { 6, 7, 8, 9, 10}
Union Array: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
So, here, though 10 is present in both arrays, we will add it only once in the union array.
What is the Intersection Of Two Arrays?
The intersection of two arrays is an array that contains only the common elements present in both arrays.
Let’s consider the following example to understand better:
Array 1: { 1, 3, 4, 6}
Array 2: { 1, 4, 5, 7}
Intersection Array: { 1, 4}
Here, 1 and 4 are common. Therefore, only they will be added to the intersection array.
Methods to Find Union Of Two Arrays
To find the union of two arrays, you can use the following four methods:
- With the help of sets
- Using map structure
- Basic method
- With the help of searching and sorting
Let’s discuss each one of them in detail.
With The Help Of Sets
The idea behind using sets is very simple. A set is a data structure which stores all the unique elements only. Therefore, the idea behind the method is to add all elements of both arrays to the set. However, the set will add only those which are unique and the common will not be repeated.
Time Complexity:
The time complexity of this method is calculated as O(m* log(m) + n* log(n)).
Using Map Data Structure
Similarly to sets, the map data structure also stores only distinct elements. Therefore, when we will store elements which are common or occur more than once in both arrays, it will store those elements only once. The idea behind this method is to use one map for both arrays and then store elements.
Time complexity:
The time complexity of this method is calculated as O(m+n).
Basic Method
This is the simplest method to find the union of two arrays. The idea behind this method is as follows:
- Declare and initialise U as an empty array.
- You will then have to copy every element of the first array into U.
- For the second array, you will have to do the following:
- In case x is not present in the first array, move X to U.
- Return the union set at the end.
Time complexity:
The time complexity of this method is calculated as O(mn).
Sorting And Searching Method
As the name suggests, this method will first sort the given arrays and then compare elements. The idea behind this method is as follows:
- Declare and initialise U as an empty array.
- Find the smallest n and m and then sort the array which is smaller
- When done, copy the smaller one to U.
- Now, for the larger array, you will have to do the following:
- Binary search the element x in the array. If x is not present, copy it to U.
- Return the union set at the end.
Time Complexity:
The time complexity of this method is calculated as O((m+n) Logm + (m+n) Logn).
Methods To Find Intersections Of Two Arrays
To find the intersection of two arrays, you can use the following two methods:
- Using the basic method
- Using the searching and sorting method.
Let’s check out both methods one-by-one.
The Basic Method
In this method, we will be checking both arrays and finding the common elements and adding them to the intersection array. The steps involved in this process are as follows:
- Declare and initialize the intersection array I as empty.
- For every element present in the first array, do the following:
- In case x is present in the second array, you will have to add it to the array I.
- In the end, you will have to return the array I.
Time complexity:
The time complexity of this method is calculated as O(mn).
The Searching And Sorting Method
The next method that you can use to find the intersection of two arrays is first sorting the given arrays and then searching the common elements. The steps involved in this process are as follows:
- Declare and initialize the intersection array I as empty.
- Find the smallest of m and n and then sort the smaller array.
- For every element present in the larger array, do the following:
- In case x is present in the smaller array, you will have to add it to the array I.
- In the end, you will have to return the array I.
Time Complexity:
The time complexity of this method is calculated as O((m+n) Logm + (m+n) Logn).
Conclusion
Working on arrays and other data structures is crucial to becoming proficient in coding. This is why interviewers ask such questions to ensure that you have a good understanding of all the concepts of coding.
To find the union and intersection of two arrays, you can use multiple methods depending on the time and space complexity.
Check out all the methods that we have mentioned and choose the one that seems efficient to you!
