Sorting: Get the intersection of 2 arrays

Problem Statement:

You are given 2 sorted arrays a[] and b[].

You need to return the intersection of the 2 arrays.

Resultant array should not have duplicate elements and the result should be in sorted manner.

Example:

Input:

a[] = {1, 1, 2, 2, 3, 6, 7, 8}

b[] = {3, 3, 3, 4, 5, 6, 6, 10}

Output

[3, 6]

Solution 1: Brute force approach

We use nested loops.

Traverse the array a[], check if it is in b[]and add to resultant array.

To void duplicates, check by matching current element with the previous element as the array is sorted.

Time Complexity: O(n * m)
Space Complexity: O(1)

Solution 2: Merge sort approach

Traverse simultaneously both a[] and b[].

If an element match in a[] and b[] add in resultant array.

If the current element is not same, check the smaller element and move forward.

Time Complexity: O(n + m)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>

using namespace std;


vector<int> solution_1 (vector<int>& a, vector<int>& b) 
{

    vector<int> result; 
    int m = a.size(); 
    int n = b.size(); 
    
    for(int i = 0; i < m; i++) 
    {
      
          if(i > 0 && a[i - 1] == a[i])
            continue;
        
         for(int j = 0; j < n; j++) 
         {
            if(a[i] == b[j]) 
            {
                result.push_back(a[i]);
                break; 
            }
        }
    }
    return result;
}


vector<int> solution_2 (vector<int>& a,  vector<int>& b) 
{

    vector<int> result; 
    int m = a.size();
    int n = b.size();
  
    int i = 0, j = 0;    
    while(i < m && j < n) 
    {
      
        if(i > 0 && a[i - 1] == a[i]) 
        {
            i++;
            continue;
        }
      
        if(a[i] < b[j]) 
        {
            i++;
        }
        else if(a[i] > b[j]) 
        {
            j++;
        }
      
        else 
        {
            result.push_back(a[i]);
            i++;
            j++;
        }
    }
    return result; 
}


int main() 
{
    vector<int> a = {1, 1, 2, 2, 3, 6, 7, 8};
    vector<int> b = {3, 3, 3, 4, 5, 6, 6, 10};

    vector<int> result = solution_1(a, b);

    for (int x : result) 
    {
        cout << x << " ";
    }

    result = solution_2(a, b);    
    for (int x : result) 
    {
        cout << x << " ";
    }


}