# Union and Intersection of Two Sorted Arrays

C++ implementation to union and intersection of two sorted arrays.
Submitted by Vikneshwar GK, on January 27, 2022

Consider 2 arrays that are sorted in ascending order. The task at hand is to find the union and intersection of these two arrays.

Example:

```Input:
test1[] = {1, 2, 4, 5, 6}
test2[] = {2, 3, 5, 7}

Output for Union: 1 2 3 4 5 6 7
Output for Intersection: 2 5

Input:
test1[] = {2, 4, 5, 7, 8}
test2[] = {1, 2, 4, 5, 8}

Output for Union: 1 2 4 5 7 8
Output for Intersection: 2 4 5 8
```

Solution 1: Finding Union

Follow the given procedure to find the union of two sorted arrays:

• Use two pointers i and j pointing starting element of array1 and array2
• Compare array1[i] and array2[j]
• If array1[i]<array2[j], print array1[i] and increment i
• If array1[i]>array2[j], print array2[j] and increment j
• If array1[i]=array2[j], print any of them and increment both i and j
• Print the remaining elements of the larger array

C++ Implementation:

```#include <bits/stdc++.h>

using namespace std;

void UnionArray(int array1[], int array2[], int length1, int length2)
{
// store max value
int max1 = array1[length1 - 1];
int max2 = array2[length2 - 1];

int ans = 0;

if (max1 > max2) {
ans = max1;
}
else
ans = max2;

int newtable[ans + 1];
memset(newtable, 0, sizeof(newtable));

// printing first element
cout << array1 << " ";

// Incrementing the First element's count
// in it's corresponding index in newtable
++newtable[array1];

// Starting traversing the first
// array from 1st index till last
for (int i = 1; i < length1; i++) {
// Checking whether current element
// is not equal to it's previous element
if (array1[i] != array1[i - 1]) {
cout << array1[i] << " ";
++newtable[array1[i]];
}
}

// Finding only non common
// elements from 2nd array
for (int j = 0; j < length2; j++) {
// By checking whether it's already
// present in newtable or not
if (newtable[array2[j]] == 0) {
cout << array2[j] << " ";
++newtable[array2[j]];
}
}
}

// Main function
int main()
{
int array1, array2, length1, length2;

cout << "Enter Number of elements for array 1: ";
cin >> length1;

for (int i = 0; i < length1; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array1[i];
}

cout << "Enter Number of elements for array 2: ";
cin >> length2;

for (int j = 0; j < length2; j++) {
cout << "Enter element " << j + 1 << ":";
cin >> array2[j];
}

UnionArray(array1, array2, length1, length2);

return 0;
}
```

Output:

```Enter Number of elements for array 1: 5
Enter element 1:1
Enter element 2:2
Enter element 3:4
Enter element 4:5
Enter element 5:6
Enter Number of elements for array 2: 4
Enter element 1:2
Enter element 2:3
Enter element 3:5
Enter element 4:7
1 2 4 5 6 3 7
```

Time Complexity: O(m+n)

Solution 2: Finding Intersection

Follow the given procedure to find the intersection of two sorted arrays:

• Use two pointers i and j pointing starting element of array1 and array2
• Compare array1[i] and array2[j]
• If array1[i]<array2[j], increment i
• If array1[i]>array2[j], increment j
• If array1[i]=array2[j], print any of them and increment both i and j

C++ Implementation:

```#include <bits/stdc++.h>

using namespace std;

void arrayIntersection(int array1[], int array2[], int length1, int length2)
{
int i = 0, j = 0;
while (i < length1 && j < length2) {
if (array1[i] < array2[j])
i++;
else if (array2[j] < array1[i])
j++;
else /* if arr1[i] == arr2[j] */
{
cout << array2[j] << " ";
i++;
j++;
}
}
}

// main function
int main()
{
int array1, array2, length1, length2;

cout << "Enter Number of elements for array 1: ";
cin >> length1;

for (int i = 0; i < length1; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array1[i];
}

cout << "Enter Number of elements for array 2: ";
cin >> length2;

for (int j = 0; j < length2; j++) {
cout << "Enter element " << j + 1 << ":";
cin >> array2[j];
}

arrayIntersection(array1, array2, length1, length2);

return 0;
}
```

Output:

```Enter Number of elements for array 1: 5
Enter element 1:2
Enter element 2:4
Enter element 3:5
Enter element 4:7
Enter element 5:8
Enter Number of elements for array 2: 5
Enter element 1:1
Enter element 2:2
Enter element 3:4
Enter element 4:5
Enter element 5:8
2 4 5 8
```

Time Complexity: O(m+n)

Preparation

What's New

Top Interview Coding Problems/Challenges!