Finding Common Elements Between Two Arrays in C++
To find the common elements in two arrays in C++, we have to first sort the arrays, then just iterate in the sorted arrays to find the common elements between those arrays.
Approach
- Sort both arrays arr1 and arr2 in non-decreasing order.
- Initialize two pointers pointer1 and pointer2 to the beginning of both arrays.
- Iterate through both arrays simultaneously:
- If the elements pointed by pointer1 and pointer2 are equal, add the element to the result vector and move both pointers forward.
- If the element in arr1 pointed by pointer1 is less than the element in arr2 pointed by pointer2, move pointer1 forward.
- If the element in arr2 pointed by pointer2 is less than the element in arr1 pointed by pointer1, move pointer2 forward.
- Repeat this process until one of the pointers reaches the end of its array.
- Return the result containing the common elements found in both arrays.
C++ Program to Find the Common Elements in Two Arrays
The below example demonstrates how we can find the common elements in two arrays in C++.
// C++ Program to illustrate how to find the common elements
// in two arrays
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<int> findCommonElements(vector<int>& arr1,
vector<int>& arr2)
{
vector<int> result;
// Sort both arrays
sort(arr1.begin(), arr1.end());
sort(arr2.begin(), arr2.end());
// Two pointers for iterating through both arrays
int pointer1 = 0;
int pointer2 = 0;
// Iterate until one of the arrays is fully traversed
while (pointer1 < arr1.size()
&& pointer2 < arr2.size()) {
if (arr1[pointer1] == arr2[pointer2]) {
// Found a common element
result.push_back(arr1[pointer1]);
pointer1++;
pointer2++;
}
else if (arr1[pointer1] < arr2[pointer2]) {
// Move pointer1 forward
pointer1++;
}
else {
// Move pointer2 forward
pointer2++;
}
}
return result;
}
int main()
{
// Sample arrays
vector<int> arr1 = { 1, 2, 3, 4, 5 };
vector<int> arr2 = { 3, 4, 5, 6, 7 };
// Find common elements
vector<int> commonElements
= findCommonElements(arr1, arr2);
// Output common elements
cout << "Common elements: ";
for (int num : commonElements) {
cout << num << " ";
}
cout << endl;
return 0;
}
Output
Common elements: 3 4 5
Time Complexity: O(N log(N)+ M log(M)), where N is the size of the first array and M is the size of the second array.
Auxilliary Space: O(N+M)
How to Find Common Elements in Two Arrays in C++?
In C++, an array is a data structure that is used to store multiple values of similar data types in a contiguous memory location. In this article, we will learn how to find the common elements in two arrays in C++.
Examples:
Input:
Arr1: {1, 2, 3, 4, 5}
Arr2: {3, 4, 5, 6, 7}
Output:
Common Elements: 3 4 5
Contact Us