Program to Find Union and Intersection of Two Sorted Arrays

  • Write a program to find union and intersection of two sorted integer array.
  • Algorithm to find union and intersection of two sorted array.

Given two sorted integer array, we have to find union and intersection of two given arrays.

Let two sorted arrays are
Array1 = [1 3 5 6 8 10 11 14 15 20]
Array2 = [2 3 5 7 9 10]
  • UNION : Union of two arrays is an array that contains all of the elements that are in at least one of the two arrays. If an element is present in both arrays or is present multiple times then we will include it in union array only once.
    • Union of above two given arrays is [1 2 3 5 6 7 8 9 10 11 14 15 20]
  • INTERSECTION : Intersection of two arrays is an array that contains all of the elements that are in both arrays.
    • Intersection of above two given arrays is [3 5 10]

Let array1 and array2 be two sorted arrays of size M and N respectively.
Union of two sorted arrays : O(M + N)
Algorithm to find union of two sorted arrays
  • Initialize two variables index1 and index2 to 0(index of smallest element of both arrays)
  • if(array1[index1] < array2[index2]) then print array1[index1] and increment index1.
  • Else if(array2[index2] < array1[index1]) then print array2[index2] and increment index2.
  • If both are equal(array2[index2] == array1[index1]) then print any one element and increment it's index.
  • If any one array ends before another then print the remaining element of another array.

C program to find union of two sorted arrays

#include <stdio.h>
/*
NOTE : In this program , we are assuming unique elements in array 
*/

/* This function prints Union of two sorted array */
void printUnion(int *array1, int size1, int *array2, int size2) {
   int index1 = 0, index2 = 0;
   /* This loop will continue untill one 
   of the array traversal completes */
   while(index1 < size1 && index2 < size2) {
      if (array1[index1] < array2[index2])
         /*array1[index1]is smaller, print it and increment index1 */ 
         printf("%d ", array1[index1++]);
      else if (array2[index2] < array1[index1])
         /*array2[index2]is smaller, print it and increment index2 */ 
         printf("%d ", array2[index2++]);
      else {
         /* Both equal, print anyone and increment both indexes */
         printf("%d ", array2[index2]);
         index1++;
         index2++;
      }
  }
 
  /* Print remianing elements */
  while(index1 < size1)
    printf("%d ", array1[index1++]);
   
  while(index2 < size2)
    printf("%d ", array2[index2++]);
}

int main(){
    int array1[10] = {1, 3, 5, 6, 8, 10, 11, 14, 15, 20};
    int array2[6] = {2, 3, 5, 7, 9, 10}; 

    printUnion(array1, 10, array2, 6);

    return 0;
}
Output
1 2 3 5 6 7 8 9 10 11 14 15 20
Intersection of two sorted arrays : O(M + N)
Algorithm to find union of two sorted arrays
  • Initialize two variables index1 and index2 to 0(index of smallest element of both arrays)
  • if(array1[index1] < array2[index2]) then increment index1.
  • Else if(array2[index2] < array1[index1]) then increment index2.
  • If both are equal(array2[index2] == array1[index1]) then print any one element and increment it's index.
  • If any one array ends before another then return.

C program to find intersection of two sorted array

#include <stdio.h>
/*
NOTE : In this program , we are assuming unique elements in array 
*/

/* This function prints Union of two sorted array */
void printIntersection(int *array1, int size1, int *array2, int size2) {
  int index1 = 0, index2 = 0;
  /* This loop will continue untill one 
  of the array traversal completes */
  while(index1 < size1 && index2 < size2) {
    if (array1[index1] < array2[index2])
    /*array1[index1]is smaller, increment index1 */ 
      index1++;
    else if (array2[index2] < array1[index1])
    /*array2[index2]is smaller, increment index2 */ 
      index2++;
    else {
    /* Both equal, print anyone and increment both indexes */
      printf("%d ", array2[index2]);
      index1++;
      index2++;
    }
  }
}

int main(){
    int array1[10] = {1, 3, 5, 6, 8, 10, 11, 14, 15, 20};
    int array2[6] = {2, 3, 5, 7, 9, 10}; 

    printIntersection(array1, 10, array2, 6);

    return 0;
}
Output
3 5 10
Posted by
Labels: ,