Find common elements in three sorted arrays

Find common elements in three sorted arrays

Given three arrays sorted in non-decreasing order, print all common elements in these arrays.

Examples:

ar1[] = {1, 5, 10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}

Output: 20, 80

ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}

Output: 5, 5

A simple solution is to first find intersection of two arrays and store the intersection in a temporary array, then find the intersection of third array and temporary array.

Time complexity of this solution is O(n1 + n2 + n3) where n1, n2 and n3 are sizes of ar1[], ar2[] and ar3[] respectively.

The above solution requires extra space and two loops, we can find the common elements using a single loop and without extra space. The idea is similar to intersection of two arrays. Like two arrays loop, we run a loop and traverse three arrays.

Let the current element traversed in ar1[] be x, in ar2[] be y and in ar3[] be z. We can have following cases inside the loop.

1) If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.
2) Else If x < y, we can move ahead in ar1[] as x cannot be a common element
3) Else If y < z, we can move ahead in ar2[] as y cannot be a common element
4) Else (We reach here when x > y and y > z), we can simply move ahead in ar3[] as z cannot be a common element.

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class FindCommonElement
{
public void findcommonElement(int arr1[],int arr2[],int arr3[])
{
int i=0, j=0 , k=0;

while(i < arr1.length && j<arr2.length && k<arr3.length)
{
if(arr1[i] == arr2[j] && arr2[j]==arr3[k])
{
System.out.print(arr1[i]+" ");  
i++;
j++;
k++;
}
else if (arr1[i] < arr2[j])
                i++;

            else if (arr2[j] < arr3[k])
                j++;

            else
                k++;
}
}

public static void main(String[] args)
{
  FindCommonElement ob = new FindCommonElement();
          int ar1[] = {1, 5, 10, 20, 40, 80};
          int ar2[] = {6, 7, 20, 80, 100};
          int ar3[] = {3, 4, 15, 20, 30, 70, 80, 120};
          System.out.print("Common elements are :");
          ob.findcommonElement(ar1, ar2, ar3);
}
}

Output:  Common elements are :20 80

Time complexity of the above solution is O(n1 + n2 + n3). 
In worst case, the largest sized array may have all small elements and middle sized array has all middle elements.