Intersection of two arrays.

Given two arrays of signed integers, give an approach to find the
intersecting set of the two arrays.

Answer:


Solution 1: O(nlog(n)) solution

void ArrayIntersection(int *a, int*b , size_t sizeA, size_t sizeB)
{
    sort(a,sizeA);
    sort(b,sizeB);
    for(size_t i =0, j=0; i < sizeA && j < sizeB; )
    {
        if (a[i] == b[j])
        {
            /* Add a[i] to output intersection list */
            ++i;++j;
            continue;
        }
        else if (a[i] < b[j] )
        {
            ++i; continue;
        }
        else if (a[i] > b[j] )
        {
            ++j; continue;
        }
    }
}

Solution 2: O(n) solution but requires at least O(n) space.
1. Scan the first array and add the elements to a lookup.
2. Scan the second array and if the element is present in the
lookup then add it to the intersection list.