Sorting: Get union of 2 sorted arrays

Problem Statement:

You are given 2 sorted arrays,

You need to return the union of union of 2 arrays such that the new array will have all distinct elements that are present in both the arrays.

Example:

Input: a[] = {1, 1, 2, 2, 2, 3}, b[] = {2, 2, 4, 4}
Output: {1, 2, 3, 4}


1, 2, 3, 4 are the distinct elements in both the arrays

Solution 1: Nested Loop

Create a nested for loop.

For each element in a[] check them in b[] and if its unique then add in resultant array.

Then for every element in b[] check in result array and if its unique add the

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

Solution 2: Merge Sort 

We use the concept of merge sort.

Take 2 pointers pointing to the starting of both the arrays.

If the element in first array is smaller, then add to the result and increment to next element

If the element in second array is smaller, then add to the result and increment to next element

If both elements are equal, then add any one of them.

While traversing the array, if the previous element is same as current element, then skip it.

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> res;
  

  	for(int i = 0; i < a.size(); i++)
    {
      
        int j;
        for (j = 0; j < res.size(); j++) 
        {
            if (res[j] == a[i]) 
                break;
        }
        if (j == res.size())
            res.push_back(a[i]);
  	}
  	
  	for(int i = 0; i < b.size(); i++)
    {
      
        int j;
        for (j = 0; j < res.size(); j++) 
        {
            if (res[j] == b[i]) 
              break;
        }
        if (j == res.size())
            res.push_back(b[i]);
  	}
    
  	sort(res.begin(), res.end());
    return res;
}

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

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

int main() 
s{
    vector<int> a = {1, 1, 2, 2, 2, 3};
    vector<int> b = {2, 2, 4, 4};

    vector<int> res = solution_1(a, b);
  
    for (int i = 0; i < res.size(); i++) 
        cout << res[i] << " ";

    cout<<endl;

    res = solution_2(a, b);
  
    for (int i = 0; i < res.size(); i++) 
        cout << res[i] << " ";

    return 0;
}

Output

1 2 3 4 
1 2 3 4