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
<?php
// PHP program to find union of
// two sorted arrays
/* Function prints union of
arr1[] and arr2[] m is the
number of elements in arr1[]
n is the number of elements
in arr2[] */
function
printUnion(
$arr1
,
$arr2
,
$m
,
$n
)
{
$i
= 0;
$j
= 0;
while
(
$i
<
$m
&&
$j
<
$n
)
{
if
(
$arr1
[
$i
] <
$arr2
[
$j
])
echo
(
$arr1
[
$i
++] .
" "
);
else
if
(
$arr2
[
$j
] <
$arr1
[
$i
])
echo
(
$arr2
[
$j
++] .
" "
);
else
{
echo
(
$arr2
[
$j
++] .
" "
);
$i
++;
}
}
// Print remaining elements
// of the larger array
while
(
$i
<
$m
)
echo
(
$arr1
[
$i
++] .
" "
);
while
(
$j
<
$n
)
echo
(
$arr2
[
$j
++] .
" "
);
}
// Driver Code
$arr1
=
array
(1, 2, 4, 5, 6);
$arr2
=
array
(2, 3, 5, 7);
$m
= sizeof(
$arr1
);
$n
= sizeof(
$arr2
);
// Function calling
printUnion(
$arr1
,
$arr2
,
$m
,
$n
);
?>
Output:
1 2 3 4 5 6 7
Time Complexity : O(m + n)