Arrays: Find the union and intersection of two sorted arrays

Question:

Given 2 sorted arrays, find the union and intersection

Example:

Input :

arr1 = {1, 3, 4, 6, 8}

arr2 = {2, 3, 5, 7, 8}

Output:

Union : {1, 2, 3, 4, 5, 6, 7, 8}
Intersection : {3, 8}

Union of 2 arrays is to print all the unique elements from both of the arrays.

Intersection of 2 arrays is to print the common elements from both of the arrays.

 

Steps to find the Union of 2 arrays:

We follow below steps to find the union of 2 arrays:

1. Take 2 variable as index_1 and index_2 and initialize them to 0.

2. Then if(arr_1[index_1] < arr_2[index_2]) then print arr_1[index_1] and increment index_1

3. else if(arr_2[index_2] < arr_1[index_1]) then print arr_2[index_2] and increment index_2

4. else if both are same, then print anyone and increment both of the index.

5. If any array ends faster than the other array, then print all the elements of other array.

Here the time complexity will be O(M + N). Because we need to traverse both the arrays.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;  

  
void print_union(int array1[], int size1, int array2[], int size2) 
{
   int index_1 = 0;
   int index_2 = 0;

   while(index_1 < size1 && index_2 < size2) 
   {
      if (array1[index_1] < array2[index_2])
      {
         cout<< array1[index_1++]<< " ";
      }
      else if (array2[index_2] < array1[index_1])
      {
         cout<< array2[index_2++]<< " ";
      }
      else 
      {
         //if both are equal, then print any one
         cout<< array2[index_2]<< " ";
         index_1++;
         index_2++;
      }
  }
  
  /* Print remianing elements */
  while(index_1 < size1)
         cout<< array1[index_1++]<< " ";
    
  while(index_2 < size2)
         cout<< array1[index_2++]<< " ";
}

int main() 
{ 
    int arr1[] = {1, 3, 4, 6, 8};

    int arr2[] = {2, 3, 5, 7, 8};

    print_union( arr1,  5, arr2,  5);

    return 0; 
} 

Output:

1 2 3 4 5 6 7 8

Steps to find the intersection of 2 arrays

We follow below steps to find the union of 2 arrays:

1. Take 2 variable as index_1 and index_2 and initialize them to 0.

2. Then if(arr_1[index_1] < arr_2[index_2]) then increment index_1

3. else if(arr_1[index_1] > arr_2[index_2]) then increment index_2

4. else if both are same, then print anyone and increment both of the index.

Here the time complexity will be O(M + N). Because we need to traverse both the arrays.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;  

  
void print_intersection(int array1[], int size1, int array2[], int size2) 
{
   int index_1 = 0;
   int index_2 = 0;

   while(index_1 < size1 && index_2 < size2) 
   {
      if (array1[index_1] < array2[index_2])
      {
         index_1++;
      }
      else if (array2[index_2] < array1[index_1])
      {
         index_2++;
      }
      else 
      {
         //if both are equal, then print any one
         cout<< array2[index_2]<< " ";
         index_1++;
         index_2++;
      }
  }
}

int main() 
{ 
    int arr1[] = {1, 3, 4, 6, 8};

    int arr2[] = {2, 3, 5, 7, 8};

    print_intersection( arr1,  5, arr2,  5);

    return 0; 
} 

Output:

3 8

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *