Intersection of Two Sorted Arrays

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 visited vector of size m (length of arr2) with all elements set to 0. This vector is used to track elements in arr2 that have already been matched.

2. Nested Loop:

• Iterate through each element of arr1 using the outer loop. For each element in arr1, iterate through each element of arr2 using the inner loop.

3. Check for Matches:

• If the current element of arr1 matches the current element of arr2 and the visited marker for that element in arr2 is 0 (indicating it has not been matched yet), add the element to the result vector temp and mark it as visited by setting the corresponding element in the visited vector to 1.

• If the current element of arr2 is greater than the current element of arr1, break out of the inner loop as the arrays are sorted and no further match will be found for the current element of arr1.

Time Complexity: O(m * n)

• Explanation: Each element in arr1 is compared with every element in arr2, resulting in a nested loop.

Space Complexity: O(m)

• Explanation: Additional space is used to store the visited vector and the result vector temp.

Example:

• Input: arr1 = [1, 2, 2, 3, 4], arr2 = [2, 2, 3, 5, 6]

• Output: intersection = [2, 2, 3]

• Explanation: Elements 2 and 3 are 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 i and j, both set to 0. These pointers will traverse arr1 and arr2, respectively.

2. Traverse Arrays:

• Use a while loop 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 arr1 is less than the current element of arr2, increment pointer i to move to the next element in arr1.

• If the current element of arr1 is greater than the current element of arr2, increment pointer j to move to the next element in arr2.

• If the current elements of both arr1 and arr2 are equal, add the element to the result vector temp and increment both pointers i and j to 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 temp stores 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 2 and 3 are 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.