Given two integer arrays arr1[] and arr2[], the task is to find the intersection of two given arrays. The resulting array must contain only unique elements and you may return the result in any order.
Example:
Input: arr1 = [1, 2, 2, 1], arr2 = [2, 2] Output: [2] Input: arr1 = [4, 9, 5], arr2 = [9, 4, 9, 8, 4] Output: [9, 4] Input: arr1 = [1, 2, 3, 4], arr2 = [5, 6, 7, 8] Output: []
Note: The intersection of two arrays is the set of elements that are common to both arrays, without any duplicates.
There are many approaches to finding the intersection of two arrays and here we are going to discuss each approach in detail with code.
Approach 1: Brute Force Approach.
This is a straightforward approach to find the intersection where each element in the first array (arr1) is checked against every element in the second array (arr2). If a match is found, the element is added to the result array.
Step-by-step Algorithm:
- Initialize an empty array to store the result.
- Iterate through each element in arr1[].
- For each element in arr1[], check if it exists in arr2[].
- If it does, add it to the result array.
C++ code Implementation.
// C++ code to find intersection of two array (Brute Force) #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> intersectionArrays(vector<int>& arr1, vector<int>& arr2) { vector<int> result; for (int num1 : arr1) { // for each element of arr1 check if exist in arr2 if (find(arr2.begin(), arr2.end(), num1) != arr2.end()) { result.push_back(num1); } } return result; } int main() { vector<int> arr1 = {4, 9, 5, 1}; vector<int> arr2 = {9, 4, 9, 8, 4}; vector<int> result = intersectionArrays(arr1, arr2); // Print the intersection array for (int i = 0; i < result.size(); ++i) { cout << result[i] << " "; } return 0; }
4 9- Time Complexity: The worst-case time complexity is O(n^2) since, in the worst case, each element of arr1 needs to be compared with each element of arr2.
- Space Complexity: O(m), where m is the number of elements in the result array.
Approach 2: Using Sorting.
This approach involves sorting both input arrays (arr1 and arr2). Then, two pointers traverse both arrays simultaneously, identifying common elements.
Step-by-step Algorithm:
- Sort both arrays, arr1[], and arr2[].
- Initialize pointers i and j to traverse arr1[] and arr2[], respectively.
- Compare elements at indices i and j.
- If the elements are equal, add the element to the result and move both pointers forward.
- If the element at arr1[i] is smaller, move the i pointer forward; otherwise, move the j pointer forward.
C++ Code Implementation.
// C++ code to find intersection of two array #include <iostream> #include <vector> #include <algorithm> using namespace std; // function to find intersection of arrays vector<int> intersectionArrays(vector<int>& arr1, vector<int>& arr2) { vector<int> result; //sorting both the array sort(arr1.begin(), arr1.end()); sort(arr2.begin(), arr2.end()); int i = 0, j = 0; while (i < arr1.size() && j < arr2.size()) { if (arr1[i] == arr2[j]) { result.push_back(arr1[i]); i++; j++; } else if (arr1[i] < arr2[j]) { i++; } else { j++; } } return result; } int main() { vector<int> arr1 = {4, 9, 5, 1}; vector<int> arr2 = {9, 4, 9, 8, 4}; vector<int> result = intersectionArrays(arr1, arr2); // Print the intersection array for (int i = 0; i < result.size(); ++i) { cout << result[i] << " "; } return 0; }
Output:
4 9- Time Complexity: O(n log n + m log m), where n and m are the sizes of arr1 and arr2, respectively, accounting for sorting.
- Space Complexity: O(1) as no additional space is required except for pointers and the result array.
Approach 3: Using Hash Set.
In this approach, a hash set is employed to store unique elements from the first array (arr1). The second array (arr2) is then traversed, and common elements are added to the result array.
Step-by-step Algorithm:
- Initialize an empty hash set to store unique elements from arr1[].
- Iterate through arr1[] and add each element to the hash set.
- Initialize an empty array to store the result.
- Iterate through arr2[].
- If an element in arr2[] is present in the hash set, add it to the result array.
C++ code Implementation.
// C++ code to find intersection of two array // using hash table #include <iostream> #include <vector> #include <unordered_set> #include <algorithm> using namespace std; // function to find intersection of arrays vector<int> intersectionArrays(vector<int>& arr1, vector<int>& arr2) { //adding unique elements of arr1 to hash set unordered_set<int> set1(arr1.begin(), arr1.end()); vector<int> result; for (int num : arr2) { if (set1.count(num)) { result.push_back(num); // To avoid duplicates in result set1.erase(num); } } return result; } int main() { vector<int> arr1 = {4, 9, 5, 1, 0}; vector<int> arr2 = {9, 4, 9, 8, 4, 1}; vector<int> result = intersectionArrays(arr1, arr2); // Print the intersection array for (int i = 0; i < result.size(); ++i) { cout << result[i] << " "; } return 0; }
Output:
4 9 1- Time Complexity: O(n + m), where n and m are the sizes of arr1 and arr2, respectively.
- Space Complexity: O(1) as no additional space is required except for pointers and the result array.
All the above approaches have different space and time complexities so you can choose which one is best for you based on your requirement to find a common intersection of two arrays.
No comments:
Post a Comment