Two Pointers: Given two arrays with duplicate, you need to return the union of two arrays

Problem Statement:

Given two sorted arrays with duplicate, you need to return the union of two arrays

Union of two arrays will have all the distinct elements present on both of the arrays.

Example:

Input:

arr_1 = [1, 2, 2, 3]

arr_2 = [3, 4, 5]

Output:

[1, 2, 3, 4, 5]

Solution 1: Bruteforce Approach

Take a set.

Add all elements from both the arrays one by one.

As set will store in sorted and duplicates will not be inserted.

Then add the elements back form set into vector and return result.

Time Complexity: O(n1Logn + n2logn + n1 + n2)
Space Complexity: O(n1+n2)

Solution 2: Two Pointer Approach

Take two pointers, each pointer pointing to one array each.

Then check the elements and insert elements accordingly into the array and return the result

Time Complexity: O(n1+n2)
Space Complexity: O(n1+n2)

Code Solution

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>

using namespace std;


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

    set<int> st;

    int n1 = a.size();
    int n2 = b.size();

    for(int i = 0; i < n1; i++)
    {
        st.insert(a[i]);
    }
    for(int i = 0; i < n2; i++)
    {
        st.insert(b[i]);
    }

    vector<int> result;

    for(auto it:st)
    {
        result.push_back(it);
    }

        return result;

}


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

        int n1 = a.size();
        int n2 = b.size();

        int i=0; 
        int j=0;

        vector<int> result;

        //check if either of the pointer reaches to end
        while(i<n1 && j<n2)
        {
        	// if current element from a is smaller
            if(a[i]<=b[j])
            {
            	//add element from array a into the result
                if(result.size()==0 || result.back()!=a[i])
                {
                    result.push_back(a[i]);
                }
                i++;
            }
            else
            {
            	//add element from array b into the result
                if(result.size()==0 || result.back()!=b[j])
                {
                    result.push_back(b[j]);
                }
                j++;
            }
        }

        //add remaining elements of arr1 to result
        while(i<n1)
        {
            if(result.size()==0 || result.back()!=a[i]){
                    result.push_back(a[i]);
            }
            i++;
        }

        //add remaining elements of arr2 to result
        while(j<n2){
            if(result.size()==0 || result.back()!=b[j]){
                    result.push_back(b[j]);
            }
            j++;
        }
        return result;
}

int main() 
{
    vector<int> arr1 = {1, 2, 2, 3, 4};
    vector<int> arr2 = {4, 4, 5};

    vector<int> result = solution_1(arr1, arr2);

    for (int val : result) 
    	cout << val << " ";

    cout<<endl;

	result = solution_2(arr1, arr2);

    for (int val : result) 
    	cout << val << " ";

    return 0;
}

Output

1 2 3 4 5 
1 2 3 4 5