Saturday, June 25, 2011

Search for Intersection Between Two Sorted Arrays of Integers

Question: there are two sorted arrays of integers such as array(1, 3, 6, 9, 10) and array(-2, 0, 4, 6, 12). Search for the intersection between these arrays. The intersection is 6 at index 2 and index 3 in the example arrays.

Solution: a naive solution would be to compare each element in the first array to each element in the second array, resulting in an O(N * M) algorithm where N and M are the numbers of elements in first and second array respectively. A better solution is using binary search for each element in the first array in the second array. That is an O(N LogM) algorithm. However, we can even do better using two array iterators at a time. Take a look at the pseudocode below:

it1, it2
while it1 < size1 and it2 < size2
  if (array1[it1] == array2[it2])
    print(it1 and it2)
    return
  else if (array1[it1] > array2[it2])
    it2++
  else
    it1++

We simply move the iterators, one for each array, whenever an element of one array is less that the element of the other array. We do this until we either find the common element (intersection) or we reach the end of any array. This works because both arrays are sorted in the ascending order. Thus, we don't have to compare each and every element to all other elements to know where the intersection is. Here is the implementation of the pseudocode in JavaScript :)

function vIntersectionInSortedArrays(cIntArray1, cIntArray2)
{
   if (cIntArray1 === null || cIntArray1 === undefined 
      || cIntArray2 === null || cIntArray2 === undefined)
   {
      document.write("Empty arrays!"); 
      return;
   }

   var nArray1It = 0;
   var nArray2It = 0;
   
   while (nArray1It < cIntArray1.length 
         && nArray2It < cIntArray2.length)
   {
      if (cIntArray1[nArray1It] == cIntArray2[nArray2It])
      {
         document.write("Intersect at index" + nArray1It 
                        + " and " + nArray2It);
         return;
      }
      else if (cIntArray1[nArray1It] > cIntArray2[nArray2It])
         nArray2It++;
      else
         nArray1It++;
   }

   document.write("No intersection!");
}

I know it's unusual to use JavaScript but a break from C++ and Java is nice. As we expect, this algorithm is more efficient. In the worst case, it takes only O(M + N) time to return the answer!

As always, thanks for following and if you have any suggestion, please don't hesitate to let me know in the comment section.

2 comments:

  1. This solution only return the first integer in both arrays. It doesn't return the whole intersection if more than one integer is in both arrays. It worth looping when we have the first hit until no other matches. Which would take O(N + M) worst case.

    ReplyDelete
  2. Yup this solution will stop at the first intersection because the problem only requires to find the intersection not all intersections. Brute force will take worst case O(N*M) while this gives worst case O(N+M).

    ReplyDelete