×

DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

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[0] << " "; // Incrementing the First element's count // in it's corresponding index in newtable ++newtable[array1[0]]; // 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[100], array2[100], 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[100], array2[100], 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)


Related Tutorials

Advertisement
Advertisement


Comments and Discussions!

Load comments ↻


Advertisement
Advertisement
Advertisement

Copyright © 2025 www.includehelp.com. All rights reserved.