Saturday, March 3, 2012

Intersection Between two arrays

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.

http://www.programcreek.com/2015/05/leetcode-intersection-of-two-arrays-java/
http://www.programcreek.com/2014/05/leetcode-intersection-of-two-arrays-ii-java/

Strategy:
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.

Code:
 #include<stdio.h>
#include<stdlib.h>

#define SIZE_A 10
#define SIZE_B 20

void intersection(int* A, int lenA, int* B, int lenB)
{
    int i=0;
    int j=0;

    while((i < lenA) && (j < lenB))
    {
        if(A[i] == B[j])
        {
            printf("%d\n", A[i]);
            i++;
            j++;
        }
        else if(A[i] < B[j])
        {
            i++;
        }
        else
        {
            j++;
        }
    }
}

int main()
{
    int A[SIZE_A];
    int B[SIZE_B];
    int i;

    for(i=0; i < SIZE_A; i++)
        A[i] = i*11;

    for(i=0; i < SIZE_B; i++)
        B[i] = i*22;

    intersection(A, SIZE_A, B, SIZE_B);
    getchar();
    return 0;
}
Time Complexity:
O(m+n) where 'm' and 'n' are the size of the arrays.

No comments:

Post a Comment