No. 24 - Intersection of Sorted Arrays

Problem: Please implement a function which gets the intersection of two sorted arrays. Assuming numbers in each array are unique.

For example, if the two sorted arrays as input are {1, 4, 7, 10, 13} and {1, 3, 5, 7, 9}, it returns an intersection array with numbers {1, 7}.

Analysis: An intuitive solution for this problem is to check whether every number in the first array (denoted as array1) is in the second array (denoted as array2). If the length of array1 is m, and the length of array2 is n, its overall time complexity is O(m*n) based on linear search. We have two better solutions.

Solution 1: With O(m+n) Time

It is noticeable that the two input arrays are sorted. Supposing a number number1 in array1 equals to a number number2 in array2, the numbers after number1 in array1 should be greater than the numbers before number2 in array2. Therefore, it is not necessary to compare the numbers after number1 in array1 with numbers before number2 in array2. It improves efficiency since many comparisons are eliminated.

The sample code for this solution is shown below:

void GetIntersection_solution1(const vector<int>& array1,

                     const vector<int>& array2,

                     vector<int>& intersection)

{

    vector<int>::const_iterator iter1 = array1.begin();

    vector<int>::const_iterator iter2 = array2.begin();

    intersection.clear();

    while(iter1 != array1.end() && iter2 != array2.end())

    {

        if(*iter1 == *iter2)

        {

            intersection.push_back(*iter1);

            ++ iter1;

            ++ iter2;

        }

        else if(*iter1 < *iter2)

            ++ iter1;

        else

            ++ iter2;

    }

}

Since it only requires to scan two arrays once, its time complexity is O(m+n).

Solution 2: With O(nlogm) Time

As we know, a binary search algorithm requires O(logm) time to find a number in an array with length m. Therefore, if we search each number of an array with length n from an array with length m, its overall time complexity is O(nlogm). If m is much greater than n, O(nlogm) is actually less than O(m+n). Therefore, we can implement a new and better solution based on binary search in such a situation. 

For instance, the following same code is suitable when array1 is much longer than array2.

/* === Supposing array1 is much longer than array2 === */

void GetIntersection_solution2(const vector<int>& array1,

                     const vector<int>& array2,

                     vector<int>& intersection)

{

    intersection.clear();

   

    vector<int>::const_iterator iter1 = array1.begin();

    while(iter1 != array1.end())

    {

        if(binary_search(array2.begin(), array2.end(), *iter1))

            intersection.push_back(*iter1);

    }

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.