Union of arrays arr1[] and arr2[] using PHP

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 :

  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

<?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)