This content originally appeared on DEV Community and was authored by Mahbub Alam Masum
Finding the intersection of two sorted arrays is a common problem in coding interviews and programming challenges. In this article, we'll discuss two approaches to solve this problem: one using a brute force approach and another using two-pointers technique.
Solution 1: Brute Force Approach (using Nested Loop)
This method involves using a nested loop to find the intersection of two arrays.
Implementation:
// Solution-1: Brute Force Approach
// Time Complexity: O(m * n)
// Space Complexity: O(m)
vector<int> intersectionOfSortedArrays(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
vector<int> temp;
vector<int> visited(m, 0);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
// If element matches and has not been matched with any element before
if (arr1[i] == arr2[j] && visited[j] == 0)
{
temp.push_back(arr2[j]);
visited[j] = 1;
break;
}
// As the array is sorted, element will not be beyond this
else if (arr2[j] > arr1[i])
{
break;
}
}
}
return temp;
}
Logic:
1. Track Visited Elements:
- Initialize a
visitedvector of sizem(length ofarr2) with all elements set to0. This vector is used to track elements inarr2that have already been matched.
2. Nested Loop:
- Iterate through each element of
arr1using the outer loop. For each element inarr1, iterate through each element ofarr2using the inner loop.
3. Check for Matches:
If the current element of
arr1matches the current element ofarr2and thevisitedmarker for that element inarr2is0(indicating it has not been matched yet), add the element to the result vectortempand mark it as visited by setting the corresponding element in thevisitedvector to1.If the current element of
arr2is greater than the current element ofarr1, break out of the inner loop as the arrays are sorted and no further match will be found for the current element ofarr1.
Time Complexity: O(m * n)
-
Explanation: Each element in
arr1is compared with every element inarr2, resulting in a nested loop.
Space Complexity: O(m)
-
Explanation: Additional space is used to store the
visitedvector and the result vectortemp.
Example:
Input:
arr1 = [1, 2, 2, 3, 4],arr2 = [2, 2, 3, 5, 6]Output:
intersection = [2, 2, 3]Explanation: Elements
2and3are common in both arrays.
Solution 2: Optimal Approach (Two-Pointers Technique)
This method uses two pointers to find the intersection efficiently.
Implementation:
// Solution-2: Optimal Approach (Using Two Pointers)
// Time Complexity: O(m + n)
// Space Complexity: O(min(n, m))
vector<int> intersectionOfSortedArrays(vector<int> &arr1, int n, vector<int> &arr2, int m)
{
int i = 0;
int j = 0;
vector<int> temp;
while (i < n && j < m)
{
if (arr1[i] < arr2[j])
{
i++;
}
else if (arr1[i] > arr2[j])
{
j++;
}
else
{
temp.push_back(arr1[i]);
i++;
j++;
}
}
return temp;
}
Logic:
1. Initialize Pointers:
- Initialize two pointers
iandj, both set to0. These pointers will traversearr1andarr2, respectively.
2. Traverse Arrays:
- Use a
whileloop to traverse both arrays as long as both pointers are within the bounds of their respective arrays.
3. Compare Elements:
If the current element of
arr1is less than the current element ofarr2, increment pointerito move to the next element inarr1.If the current element of
arr1is greater than the current element ofarr2, increment pointerjto move to the next element inarr2.If the current elements of both
arr1andarr2are equal, add the element to the result vectortempand increment both pointersiandjto move to the next elements in both arrays.
Time Complexity: O(m + n)
- Explanation: Each array is traversed once using two pointers.
Space Complexity: O(min(n, m))
-
Explanation: The result vector
tempstores the intersection elements, which can be up to the size of the smaller array.
Example:
Input:
arr1 = [1, 2, 2, 3, 4],arr2 = [2, 2, 3, 5, 6]Output:
intersection = [2, 2, 3]Explanation: Elements
2and3are common in both arrays.
Comparison
-
Brute Force Approach:
- Pros: Simple and straightforward.
- Cons: Inefficient for large arrays due to O(m * n) time complexity and additional space usage.
-
Optimal Approach:
- Pros: Efficient with O(m + n) time complexity and lower space complexity.
- Cons: Slightly more complex to implement but highly efficient for large arrays.
Edge Cases
Empty Arrays: Returns an empty array as there are no elements to intersect.
No Intersection: Returns an empty array if there are no common elements.
Identical Arrays: Returns the entire array as all elements are common.
Additional Notes
Efficiency: The two-pointers technique is more time-efficient, making it preferable for large arrays.
Practicality: Both methods handle intersections efficiently but the choice depends on the size of the arrays and space constraints.
Conclusion
Finding the intersection of two sorted arrays can be efficiently achieved using either a brute force approach or a two-pointers technique. The optimal choice depends on the specific constraints and requirements of the problem.
This content originally appeared on DEV Community and was authored by Mahbub Alam Masum
Mahbub Alam Masum | Sciencx (2024-06-20T18:44:03+00:00) Intersection of Two Sorted Arrays. Retrieved from https://www.scien.cx/2024/06/20/intersection-of-two-sorted-arrays/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.