Find Intersection of Two Arrays - C, C++ Program

Write a C, C++ program to find intersection of two arrays. Given a two sorted arrays, we need to write a code to find intersection of two arrays.

Suppose, we have given following two arrays.

int arr1[] = { 1, 3, 4, 5}
int arr2[] = { 1, 2, 3, 4, 5}

Intersection of arr1 and arr2 is 1, 3, 4, 5.

Let's discuss how to solve this problem.

Practice question on arrays

C, C++ interview questions

How to Find Intersection of Two Arrays

METHOD 1:  Naive approach

Easiest approach is to solve this problem using two for loops. But the time complexity of using two for loops is O(n²).

   /* Suppose len1 and len2 is the length of 
      first and second array. */

     for(int i=0; i < len1; i++) {

            for(int j = 0; j < len2; j++) {

                if( arr1[i] == arr2[j] ) {

                    cout << arr1[i];

                 }
            }
        }

METHOD 2:

 1. Use two indexes p and q.

 2. Run a while loop and check

 a) If firstarray[p] > secondarray[q] then increment q.

 b) If secondarra[q] > firstarray[p] then increment p.

 c) If firstarray[p] == secondarray[q] then increment p and q.

Time complexity of this solution is O(m + n), where m and n is the length of first and second array.

Sorting algorithms and their time complexity .

Let's implement method 2 solution.

Find Intersection of Two Arrays in C++

#include <iostream>
using namespace std;

int main() {
 
   int arr1[100], arr2[100], len1, len2, i, p = 0, q = 0;
 
   cout << "Enter lenght of first array (Max 100) \n";
   cin  >> len1;
 
   cout << " Enter sorted values for first array \n";
 
   for (i = 0; i < len1; i++) {
  
      cin >> arr1[i];
  
   }
 
   cout << "Enter length of second array (Max 100) \n";
   cin  >> len2;
 
   cout << " Enter sorted values for second array \n";
 
   for (i = 0; i < len2; i++) {
  
      cin >> arr2[i];
  
   }
 
 
   while (p <= len1 && q <= len2) {
  
      if (arr1[p] < arr2[q]) {
   
         p++;
   
      } else if (arr2[q] < arr1[p]) {
   
         q++;
   
      } else if (arr1[p] == arr2[q]) {
   
         cout << arr1[p] <<" ";
   
         p++;
         q++;
   
      }
  
   }
 
   return 0;
}

Output :

Enter length of first array (Max 100) :  4

Enter sorted values for first array :
1
3
4
5

Enter length of second array (Max 100): 5

Enter sorted values for second array :
1
2
3
4
5

Intersection of two arrays :  1  3   4   5

Find Intersection of Two Arrays in C

#include <stdio.h>

int main(void) {
 
   int arr1[100], arr2[100], len1, len2, i, p = 0, q = 0;
 
   printf( "Enter lenght of first array (Max 100) \n");
   scanf( " %d ", &len1);
 
   printf( " Enter sorted values for first array \n");
 
   for (i = 0; i < len1; i++) {
  
      scanf(" %d ", &arr1[i]);
  
   }
 
   printf( "Enter length of second array (Max 100) \n");
   scanf  (" %d ", &len2);
 
   printf (" Enter sorted values for second array \n");
 
   for (i = 0; i < len2; i++) {
  
      scanf( " %d ", &arr2[i]);
  
   }
 
 
   while (p <= len1 && q <= len2) {
  
      if (arr1[p] < arr2[q]) {
   
         p++;
   
      } else if (arr2[q] < arr1[p]) {
   
         q++;
   
      } else if (arr1[p] == arr2[q]) {
   
         printf (" %d  ", arr1[p]);
   
         p++;
         q++;
   
      }
  
   }
 
   return 0;
}