Given two arrays, find all elements that appear in both arrays. Return the common elements without duplicates, in any order. If no common element exists, return an empty array.
Example 1
Input: a = [1, 2, 3, 4], b = [3, 4, 5, 6]
Output: [3, 4]
Explanation: 3 appears in both arrays and 4 appears in both arrays. 1 and 2 exist only in the first array. 5 and 6 exist only in the second array.
Example 2
Input: a = [1, 2, 1, 3], b = [2, 2, 3, 4]
Output: [2, 3]
Explanation: Even though 2 appears twice in both arrays and 1 appears twice in the first, we report each common value exactly once. 1 does not appear in the second array so it is excluded.
Brute Force Approach
The simplest idea is to compare every element of the first array with every element of the second array. Whenever a unique common value is found, it is included in the answer.
Algorithm
If either array is empty, no common element exists, so return an empty array.
Pick one element from the first array and search for the same element in the second array.
Whenever a common element is found, it is added in the answer if not already present.
Continue until the first array is completely traversed, then return the final answer.
Dry Run
Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds unique common elements using direct searching vector<int> commonElements(vector<int> a, vector<int> b) { vector<int> answer; // Empty input cannot have common elements if (a.empty() || b.empty()) { return answer; } // Check every value from the first array for (int firstValue : a) { bool foundInSecond = false; // Search the second array for the current value for (int secondValue : b) { // Matching value means the current value is common if (firstValue == secondValue) { foundInSecond = true; break; } } bool alreadyAdded = false; // Check the answer to avoid duplicate output values for (int value : answer) { // Existing answer value should not be added again if (value == firstValue) { alreadyAdded = true; break; } } // Add only values that are common and not already present if (foundInSecond && !alreadyAdded) { answer.push_back(firstValue); } } return answer; }};// Driver code starts// Runs a sample test for the brute force solutionint main() { vector<int> a = {1, 2, 1, 3}; vector<int> b = {2, 2, 3, 4}; Solution solution; vector<int> answer = solution.commonElements(a, b); // Print the returned array as space-separated values for (int i = 0; i < answer.size(); i++) { // Add a space before every element except the first if (i > 0) { cout << " "; } cout << answer[i]; } cout << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N × M + N × R), where N and M are the sizes of the first and second arrays, respectively, and R is the number of common values stored. Each value from the first array is compared with all elements of the second array, and duplicate checking scans the current answer.
Space Complexity: O(R), where R is the number of common values stored in the answer.
Better Approach
The brute force approach ends up searching the same array repeatedly, even for values that have already been checked. By sorting both arrays first, equal elements become adjacent. This helps to continue the comparison effectively instead of traversing the whole array every time.
Algorithm
If either array is empty, no common elements exist, so return an empty array.
Now both arrays can be sorted and a pointer can be placed at the beginning of each array.
Compare the values at both pointers while both pointers remain inside the arrays.
Whenever the values are equal, add the common element, and both pointers can be moved past all duplicate occurrences of that value.
If the values are different, move the pointer pointing to the smaller value.
Continue until one of the arrays has been completely processed, then return the collected common elements.
Dry Run
Better
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds unique common elements using sorting and two pointers vector<int> commonElements(vector<int> a, vector<int> b) { vector<int> answer; // Empty input cannot have common elements if (a.empty() || b.empty()) { return answer; } sort(a.begin(), a.end()); sort(b.begin(), b.end()); int firstIndex = 0; int secondIndex = 0; // Walk through both sorted arrays while (firstIndex < a.size() && secondIndex < b.size()) { // Equal values are common if (a[firstIndex] == b[secondIndex]) { int commonValue = a[firstIndex]; // Add only the first copy of a common value if (answer.empty() || answer.back() != commonValue) { answer.push_back(commonValue); } // Skip all copies in the first array while (firstIndex < a.size() && a[firstIndex] == commonValue) { firstIndex++; } // Skip all copies in the second array while (secondIndex < b.size() && b[secondIndex] == commonValue) { secondIndex++; } } // Smaller first-array value cannot match later else if (a[firstIndex] < b[secondIndex]) { firstIndex++; } // Smaller second-array value cannot match later else { secondIndex++; } } return answer; }};// Driver code starts// Runs a sample test for the sorting solutionint main() { vector<int> a = {1, 2, 1, 3}; vector<int> b = {2, 2, 3, 4}; Solution solution; vector<int> answer = solution.commonElements(a, b); // Print the returned array as space-separated values for (int i = 0; i < answer.size(); i++) { // Add a space before every element except the first if (i > 0) { cout << " "; } cout << answer[i]; } cout << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N log(N) + M log(M)), where N and M are the sizes of the first and second arrays, respectively. Both arrays are sorted first, followed by a single traversal of the two arrays.
Space Complexity: O(R), where R is the number of common values stored in the answer.
Optimal Approach
The previous approach sorts both arrays so they can be compared efficiently. In reality, the only thing that matters is whether a value from one array is present in the other.
A hash set can check it quickly. Once all elements of the first array have been stored in a hash set, the second array can be scanned directly, and every common element can be collected easily.
Algorithm
If either array is empty, no common elements exist, so return an empty array.
Now all elements of the first array can be stored in a hash set.
Traverse the second array and check whether each element is present in the hash set.
Whenever a common element is found, add it to another hash set so that duplicate values are ignored automatically.
Convert the answer set into an array after the traversal is complete and return the resulting array as answer.
Dry Run
Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds unique common elements using hash sets vector<int> commonElements(vector<int> a, vector<int> b) { vector<int> answer; // Empty input cannot have common elements if (a.empty() || b.empty()) { return answer; } unordered_set<int> firstValues; unordered_set<int> commonValues; // Store all values from the first array for (int value : a) { firstValues.insert(value); } // Scan the second array and keep only common values for (int value : b) { // Value is common when the first set contains the same value if (firstValues.find(value) != firstValues.end()) { commonValues.insert(value); } } // Convert the set into an array result for (int value : commonValues) { answer.push_back(value); } return answer; }};// Driver code starts// Runs a sample test for the hash set solutionint main() { vector<int> a = {1, 2, 1, 3}; vector<int> b = {2, 2, 3, 4}; Solution solution; vector<int> answer = solution.commonElements(a, b); sort(answer.begin(), answer.end()); // Print the returned array as space-separated values for (int i = 0; i < answer.size(); i++) { // Add a space before every element except the first if (i > 0) { cout << " "; } cout << answer[i]; } cout << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N + M) on average, where N and M are the sizes of the first and second arrays, respectively. The first array is stored in a hash set, and the second array is scanned once.
Space Complexity: O(N + R), where N is the number of elements in the first array and R is the number of unique common values stored in the answer set.
Be the first to add a comment.