# Programming Videos

## Search

### 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(n2).

```   /* 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, arr2, 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, arr2, 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;
}

```