Tuesday, May 14, 2013

Common elements between two sorted arrays

Given two sorted arrays, how do you efficiently find the common elements between those two?

Method#1:
Simple and Brute-force approach
Iterate through one array, and try to find the element in another array using linear search. If it is found, then print it. This approach takes O(n^2) time as for each element in the first array we doing a linear search in the second array which takes O(n). So for n elements it would be O(n^2).

Method#2:
Better approach with binary search
This approach is simliar to the first one except that it uses binary search instead of linear search for finding an element in the second array as the arrays are sorted. Binary search takes O(log n) for each element. So for n elements the time complexity would be O(n log n).

Method#3:
Efficient
This method fully utilizes the fact that both arrays are sorted. Start with two indices pointing to beginning of the arrays. If the elements pointed by these indices are same, then it is a common element, and we advance both the pointers. If one element is smaller, then advance that pointer (in hope of finding the next equal element). Continue this until any one of the two indices reaches their end.

Here is the C++ code which implements the third approach.

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

using namespace std;

//prints the intersection of two sorted arrays
//duplicates are allowed
void printIntersect(vector<int>& s1, vector<int>& s2)
{
 //i and j start 0 i.e first element
 int i = 0 , j= 0;

 //while either of the two indices reaches end
 while ( i < s1.size() && j < s2.size() )
 {
  //if first array element is lesser, advance that index by one
  if( s1[i] < s2[j] )
  {
   i++;
  }
  //otherwise advance second index
  else if( s1[i] > s2[j] )
  {
   j++;
  }
  //both elements are same, print it, and advance both the pointers 
  else
  {
   cout<<s1[i]<<" ";
   i++;
   j++;
  }
 }
}

int main()
{
 vector<int> set1, set2;
 int n1,n2; //size of the sets
 cin>>n1>>n2;

 int i;
 //read two arrays
 for( i = 0 ; i < n1; i++ )
 {
  int d;
  cin>>d;
  set1.push_back(d);
 }
 for( i = 0 ; i < n2; i++ )
 {
  int d;
  cin>>d;
  set2.push_back(d);
 }
 printIntersect(set1,set2);
 return 0;
}