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
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)
Another Method to Find Common Elements Using Set
To find the common elements in two arrays in C++, we have to create a set from the elements of the first array. Iterate through the second array and add elements that exist in the set to the result vector, returning it as the final output.
Approach
- Initialize an unordered set to store elements from the first array.
- Iterate through the first array and insert each element into the set.
- Iterate through the second array:
- For each element, check if it exists in the set:
- If it does, add it to the result vector.
- Return the result vector containing common elements.
C++ Program to Find the Common Elements in Two Arrays Using Set
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 <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
// Function to find common elements between two vectors
vector<int> findCommonElements(const vector<int>& arr1,
const vector<int>& arr2)
{
unordered_set<int> set;
vector<int> result;
// Insert all elements of first vector into set
for (int num : arr1)
set.insert(num);
// Check elements of second vector
for (int num : arr2) {
// If element is present in set, it's common
if (set.find(num) != set.end())
result.push_back(num);
}
return result;
}
int main()
{
vector<int> arr1 = { 1, 2, 3, 4, 5 };
vector<int> arr2 = { 3, 4, 5, 6, 7 };
vector<int> commonElements
= findCommonElements(arr1, arr2);
if (commonElements.empty()) {
cout << "No common elements found." << endl;
}
else {
cout << "Common elements: ";
for (int elem : commonElements)
cout << elem << " ";
cout << endl;
}
return 0;
}
Output
Common elements: 3 4 5
Time Complexity: O(N+ M), where N is the size of the first array and M is the size of the second array.
Auxilliary Space: O(N+M)
Contact Us