# Find Union and Intersection of 2 sorted arrays

Union refers to the set of all the elements of the 2 arrays. Intersection here refers to the set of elements which are common in both the arrays.

Steps to find union of 2 arrays:

1) i and j, initial values i = 0, j = 0
2) If a1[i] < a2[j] then print a1[i] and increment i.
3) If a1[i] > a2[j] then print a2[j] and increment j.
4) If a1[i]=a2[j] then print a1[i] increment both i and j.
5) Print remaining elements of the larger array.

int find_union(int arr1[], int arr2[], int SIZE1, int SIZE2)
{
int i = 0, j = 0;
while(i < SIZE1 && j < SIZE2)
{
if(arr1[i] < arr2[j])
printf(" %d ", arr1[i++]);
else if(arr2[j] < arr1[i])
printf(" %d ", arr2[j++]);
else
{
printf(" %d ", arr1[i]);
i++; j++;
}
}

/* Print remaining elements of the larger array */
while(i < SIZE1)
printf(" %d ", arr1[i++]);
while(j < SIZE2)
printf(" %d ", arr2[j++]);
}

Complexity: O(N) N is size of larger array

Steps to find intersection of 2 arrays:

1) i and j, initial values i = 0, j = 0
2) If a1[i] < a2[j] then increment i.
3) If a1[i] > a2[j] then increment j.
4) If a1[i]=a2[j] then print a1[i] increment both i and j.

int find_intersection(int arr1[], int arr2[], int SIZE1, int SIZE2)
{
int i = 0, j = 0;
while(i < SIZE1 && j < SIZE2)
{
if(arr1[i] < arr2[j])
i++;
else if(arr2[j] < arr1[i])
j++;
else
{
printf(" %d ", arr1[i]);
i++; j++;
}
}

}

Complexity: O(N), N is size of larger array

### 3 Thoughts on “Find Union and Intersection of 2 sorted arrays”

1. gaurav on July 16, 2013 at 4:44 am said:

these methods will work only when arrays are sorted na??

2. crazyadmin on July 16, 2013 at 9:26 am said:

Yes, Otherwise you will have to sort the arrays.. Use Quick Sort for O(N logN)

3. Dinesh on May 2, 2016 at 4:07 pm said:

Above union code will fail if the input will be like below

Array1 = (1, 3, 4, 5, 7, 8)
Array2 = (2, 3, 5, 16)

Am i right?