Intersection of two sorted arrays
Given two sorted arrays, find their union and intersection.
Example:
Input : arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Output : Union : {1, 2, 3, 4, 5, 6, 7}
Intersection : {3, 5}
Input : arr1[] = {2, 5, 6}
arr2[] = {4, 6, 8, 10}
Output : Union : {2, 4, 5, 6, 8, 10}
Intersection : {6}
We strongly recommend that you click here and practice it,
before moving on to the solution.
Union of arrays arr1[] and arr2[]
To find union of two sorted arrays, follow the following merge procedure :
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i.
3) If arr1[i] is greater than arr2[j] then print arr2[j] and increment j.
4) If both are same then print any of them and increment both i and j.
5) Print remaining elements of the larger array.
Below is the implementation of the above approach :
C++ C Java Python3 C# PHP Javascript
// C++ program to find union of
// two sorted arrays
#include <bits/stdc++.h>
using namespace std;
/* Function prints union of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
void printUnion(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j])
cout << arr1[i++] << " ";
else if (arr2[j] < arr1[i])
cout << arr2[j++] << " ";
else {
cout << arr2[j++] << " ";
i++;
}
}
/* Print remaining elements of the larger array */
while (i < m)
cout << arr1[i++] << " ";
while (j < n)
cout << arr2[j++] << " ";
}
/* Driver program to test above function */
int main()
{
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
// Function calling
printUnion(arr1, arr2, m, n);
return 0;
}
Output:
1 2 3 4 5 6 7
Time Complexity : O(m + n)
Handling duplicates in any of the array : Above code does not handle duplicates in any of the array. To handle the duplicates,
just check for every element whether adjacent elements are equal.
Below is the implementation of this approach.
C++ Java Python3 C# Javascript
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
static void UnionArray(int arr1[],
int arr2[], int l1, int l2)
{
// Taking max element present in either array
int m = arr1[l1 - 1];
int n = arr2[l2 - 1];
int ans = 0;
if (m > n) {
ans = m;
}
else
ans = n;
// Finding elements from 1st array
// (non duplicates only). Using
// another array for storing union
// elements of both arrays
// Assuming max element present
// in array is not more than 10^7
int newtable[ans + 1];
memset(newtable,0,sizeof(newtable));
// First element is always
// present in final answer
cout << arr1[0] << " ";
// Incrementing the First element's count
// in it's corresponding index in newtable
++newtable[arr1[0]];
// Starting traversing the first
// array from 1st index till last
for (int i = 1; i < l1; i++) {
// Checking whether current element
// is not equal to it's previous element
if (arr1[i] != arr1[i - 1]) {
cout << arr1[i] << " ";
++newtable[arr1[i]];
}
}
// Finding only non common
// elements from 2nd array
for (int j = 0; j < l2; j++) {
// By checking whether it's already
// present in newtable or not
if (newtable[arr2[j]] == 0) {
cout << arr2[j] << " ";
++newtable[arr2[j]];
}
}
}
// Driver Code
int main()
{
int arr1[] = { 1, 2, 2, 2, 3 };
int arr2[] = { 2, 3, 4, 5 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int m = sizeof(arr2) / sizeof(arr2[0]);
UnionArray(arr1, arr2, n, m);
return 0;
}
// This code is contributed by splevel62.
Output
1 2 3
Thanks to Sanjay Kumar for suggesting this solution.
Another Approach using TreeSet in Java: The idea of the approach is to build a TreeSet and insert all the elements from both
arrays into it. As a tree set stores only unique values, it will only keep all the unique values of both arrays.
Below is the implementation of the approach.
Java
// Java code to implement the approach
import [Link].*;
import [Link].*;
class GFG {
// Function to return the union of two arrays
public static ArrayList<Integer>
Unionarray(int arr1[], int arr2[],
int n, int m)
{
TreeSet<Integer> set = new TreeSet<>();
// Remove the duplicates from arr1[]
for (int i : arr1)
[Link](i);
// Remove duplicates from arr2[]
for (int i : arr2)
[Link](i);
// Loading set to array list
ArrayList<Integer> list
= new ArrayList<>();
for (int i : set)
[Link](i);
return list;
}
// Driver code
public static void main(String[] args)
{
int arr1[] = { 1, 2, 2, 2, 3 };
int arr2[] = { 2, 3, 3, 4, 5, 5 };
int n = [Link];
int m = [Link];
// Function call
ArrayList<Integer> uni
= Unionarray(arr1, arr2, n, m);
for (int i : uni) {
[Link](i + " ");
}
}
}
// Contributed by ARAVA SAI TEJA
Output
1 2 3 4 5
Time Complexity: O(m + n) where 'm' and 'n' are the size of the arrays
Auxiliary Space: O(m + n)
Thanks to Arava Sai Teja for suggesting this solution.
Another optimized approach: In the above code we use some extra auxiliary space by creating newtable[ ]. We can reduce the
space complexity program to test above functionto constant by checking adjacent elements when incrementing i or j such
that i or j directly move to the next distinct element. We can perform this operation in-place (i.e. without using any extra space).
C++
// This implementation uses vectors but can be easily modified to adapt arrays
#include <bits/stdc++.h>
using namespace std;
/* Helper function for printUnion().
This same function can also be implemented as a lambda function inside printUnion().
*/
void next_distinct(const vector<int> &arr, int &x) // Moving to next distinct element
{
// vector CAN be passed by reference to avoid unnecessary copies.
// x(index) MUST be passed by reference so to reflect the change in the original index parameter
/* Checks whether the previous element is equal to the current element,
if true move to the element at the next index else return with the current index
*/
do
{
++x;
} while (x < [Link]() && arr[x - 1] == arr[x]);
}
void printUnion(vector<int> arr1, vector<int> arr2)
{
int i = 0, j = 0;
while (i < [Link]() && j < [Link]())
{
if (arr1[i] < arr2[j])
{
cout << arr1[i] << " ";
next_distinct(arr1, i); // Incrementing i to next distinct element
}
else if (arr1[i] > arr2[j])
{
cout << arr2[j] << " ";
next_distinct(arr2, j); // Incrementing j to next distinct element
}
else
{
cout << arr1[i] << " ";
// OR cout << arr2[j] << " ";
next_distinct(arr1, i); // Incrementing i to next distinct element
next_distinct(arr2, j); // Incrementing j to next distinct element
}
}
// Remaining elements of the larger array
while (i < [Link]())
{
cout << arr1[i] << " ";
next_distinct(arr1, i); // Incrementing i to next distinct element
}
while (j < [Link]())
{
cout << arr2[j] << " ";
next_distinct(arr2, j); // Incrementing j to next distinct element
}
}
int main()
{
vector<int> arr1 = {1, 2, 2, 2, 3}; // Duplicates Present
vector<int> arr2 = {2, 3, 3, 4, 5, 5}; // Duplicates Present
printUnion(arr1, arr2);
return 0;
}
// This code is contributed by ciphersaini.
Output
1 2 3 4 5
Time Complexity: where m & n are the sizes of the arrays.
Auxiliary Space:
Intersection of arrays arr1[] and arr2[]
To find intersection of 2 sorted arrays, follow the below approach :
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then increment i.
3) If arr1[i] is greater than arr2[j] then increment j.
4) If both are same then print any of them and increment both i and j.
Below is the implementation of the above approach :
C++ C Java Python3 C# PHP Javascript
// C++ program to find intersection of
// two sorted arrays
#include <bits/stdc++.h>
using namespace std;
/* Function prints Intersection of arr1[] and arr2[]
m is the number of elements in arr1[]
n is the number of elements in arr2[] */
void printIntersection(int arr1[], int arr2[], int m, int n)
{
int i = 0, j = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j])
i++;
else if (arr2[j] < arr1[i])
j++;
else /* if arr1[i] == arr2[j] */
{
cout << arr2[j] << " ";
i++;
j++;
}
}
}
/* Driver program to test above function */
int main()
{
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int m = sizeof(arr1) / sizeof(arr1[0]);
int n = sizeof(arr2) / sizeof(arr2[0]);
// Function calling
printIntersection(arr1, arr2, m, n);
return 0;
}
Output:
2 5
Time Complexity : O(m + n)
Handling duplicate in Arrays :
Above code does not handle duplicate elements in arrays. The intersection should not count duplicate elements. To handle
duplicates just check whether current element is already present in intersection list. Below is the implementation of this
approach.
Python3 Javascript C++ Java
# Python3 program to find Intersection of two
# Sorted Arrays (Handling Duplicates)
def IntersectionArray(a, b, n, m):
'''
:param a: given sorted array a
:param n: size of sorted array a
:param b: given sorted array b
:param m: size of sorted array b
:return: array of intersection of two array or -1
'''
Intersection = []
i = j = 0
while i < n and j < m:
if a[i] == b[j]:
# If duplicate already present in Intersection list
if len(Intersection) > 0 and Intersection[-1] == a[i]:
i+= 1
j+= 1
# If no duplicate is present in Intersection list
else:
[Link](a[i])
i+= 1
j+= 1
elif a[i] < b[j]:
i+= 1
else:
j+= 1
if not len(Intersection):
return [-1]
return Intersection
# Driver Code
if __name__ == "__main__":
arr1 = [1, 2, 2, 3, 4]
arr2 = [2, 2, 4, 6, 7, 8]
l = IntersectionArray(arr1, arr2, len(arr1), len(arr2))
print(*l)
# This code is contributed by Abhishek Kumar
Output
2 4
Time Complexity : O(m + n)
Auxiliary Space : O(min(m, n))
Another Approach using Tree Set: The idea of this approach is to build a tree set to store the unique elements of arri[]. Then
compare the elements arr2[] with the tree set and also check if that is considered in the intersection to avoid duplicates.
Below is the implementation of the approach.
Java
// Java code to implement the approach
import [Link].*;
import [Link].*;
class GFG {
// Function to find the intersection
// of two arrays
public static ArrayList<Integer>
Intersection(int arr1[], int arr2[],
int n, int m)
{
TreeSet<Integer> set = new TreeSet<>();
// Removing duplicates from first array
for (int i : arr1)
[Link](i);
ArrayList<Integer> list
= new ArrayList<>();
// Avoiding duplicates and
// adding intersections
for (int i : arr2)
if ([Link](i)
&& )
[Link](i);
// Sorting
[Link](list);
return list;
}
// Driver code
public static void main(String[] args)
{
int arr1[] = { 1, 2, 4, 5, 6 };
int arr2[] = { 2, 3, 5, 7 };
int n = [Link];
int m = [Link];
// Function call
ArrayList<Integer> inter
= Intersection(arr1, arr2, n, m);
for (int i : inter) {
[Link](i + " ");
}
}
}
// Contributed by ARAVA SAI TEJA
Output
2 5
Time Complexity: O(m+n)
Auxiliary Space: O(m+n)
Thanks to Arava Sai Teja for suggesting this solution.
Another approach that is useful when difference between sizes of two given arrays is significant.
The idea is to iterate through the shorter array and do a binary search for every element of short array in big array (note that
arrays are sorted). Time complexity of this solution is O(min(mLogn, nLogm)). This solution works better than the above
approach when ratio of larger length to smaller is more than logarithmic order.