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}
Union of arrays arr1[] and arr2[]
To find union of two sorted arrays, follow the following merge procedure :
- Use two index variables i and j, initial values i = 0, j = 0
- If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i.
- If arr1[i] is greater than arr2[j] then print arr2[j] and increment j.
- If both are same then print any of them and increment both i and j.
- Print remaining elements of the larger array.
Below is the implementation of the above approach :
// 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.
// Java program to find union of two
// sorted arrays (Handling Duplicates)
class
FindUnion {
static
void
UnionArray(
int
arr1[],
int
arr2[])
{
// Taking max element present in either array
int
m = arr1[arr1.length -
1
];
int
n = arr2[arr2.length -
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[] =
new
int
[ans +
1
];
// First element is always
// present in final answer
System.out.print(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 < arr1.length; i++) {
// Checking whether current element
// is not equal to it's previous element
if
(arr1[i] != arr1[i -
1
]) {
System.out.print(arr1[i] +
" "
);
++newtable[arr1[i]];
}
}
// Finding only non common
// elements from 2nd array
for
(
int
j =
0
; j < arr2.length; j++) {
// By checking whether it's already
// present in newtable or not
if
(newtable[arr2[j]] ==
0
) {
System.out.print(arr2[j] +
" "
);
++newtable[arr2[j]];
}
}
}
// Driver Code
public
static
void
main(String args[])
{
int
arr1[] = {
1
,
2
,
2
,
2
,
3
};
int
arr2[] = {
2
,
3
,
4
,
5
};
UnionArray(arr1, arr2);
}
}
Intersection of arrays arr1[] and arr2[]
To find intersection of 2 sorted arrays, follow the below approach :
- Use two index variables i and j, initial values i = 0, j = 0
- If arr1[i] is smaller than arr2[j] then increment i.
- If arr1[i] is greater than arr2[j] then increment j.
- If both are same then print any of them and increment both i and j.
Below is the implementation of the above approach :
// 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)