Intersection of 2 Arrays

Given 2 Arrays a1,a2 of length n1 and n2 respectively, Find its Intersection. If there is no intersection print "Intersection does not exist"

Naive Approach:

The naive approach  would be to compare all possible pairs of elements from both arrays and output the ones that match. This would take O(n1*n2).

Better Approach:

• Sort both the arrays
• Take two indexes pointing to start of both arrays.
• Now start comparing elements of both the array till either of indexes reaches the end.
• If 2 elements are equal, increments both the indexes.
• Otherwise increment the index whose array element has less value.

Complexity is O(n1logn1 +n2logn2  +n1+n2) = O(nlogn)

Input:       Two  integer arrays a1 and a2  of different sizes n1 and n2 respectively.

Output:     Elements that appear in both a1 and a2
Example:  For input a1 = {3,6,7,11,9} and b1 = {4,5,6,9,3,11}                 
                 Output should be {3,6,9,11}

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

using namespace std;

vector<int> Intersection ( int *a1,int *a2,int n1,int n2 )
{
    vector<int> v;
    int i=0,j=0;
    sort ( a1,a1+n1 );  // O(n1logn1) complexity
    sort ( a2,a2+n2 );
    while ( i<n1&&j<n2 )
    {
        if ( a1[i]==a2[j] )
        {
            v.push_back ( a1[i] );
            i++,j++;
        }
        else
            if ( a1[i]>a2[j] )
            {
                j++;
            }
            else {
                i++;
            }

    }
    return v;
}
int main()
{
    int n1,n2;
    cin>>n1>>n2;
    int *a1=new int[n1];
    int *a2=new int[n2];
    for ( int i=0; i<n1; i++ )
    {
        cin>>a1[i];
    }
    for ( int i=0; i<n2; i++ )
    {
        cin>>a2[i];
    }
    vector<int> res=Intersection ( a1,a2,n1,n2 );
    if ( res.size() ==0 ) {
        cout<<"Intersection does not exist";
    }
    else
    {
        for ( vector<int>::iterator i=res.begin(); i!=res.end(); i++ )
        {
            cout<<*i<<" ";
        }
    }
    getchar();


}

Please comment if you find anything incorrect or have any other inputs.