Find common elements in 3 sorted arrays

Find common elements in 3 sorted array

3 arrays are given:

Arr1: 4,19,33,47,68,79,82,85,100

Arr2: 18,19 ,20,33,79, 80, 100

Arr3: 1,2,4,33,64,68,79,100,128,139

Out of all these,

    33,79,100 are the elements that are common in given 3 arrays.

Brute force approach :

Pick first element in arr1 and check if it is present in 2^nd and 3^rd array also. If yes then print it, otherwise pick second element, then third element and so on.

Time complexity : O(n³ )

An efficient approach :

Algorithm :

Step 1: Initialize i=0,j=0,k=0;

Step 2 :Repeat this step till i<len(arr1) and j<len(arr2) and k <len(arr3)

A)If arr1[i]=arr2[j]=arr3[k] ,print that element as it is the common element and increment i,j,k.

B) Else if arr1[i] < arr2[j] ,then arr1[i] cannot be the common element of 3 arrays as arr2 has already moved ahead. Increment i.

C)  Else if arr2[j]< arr3[k] , then arr2[j] cannot be the common element. Increment j.

D)Else increment k. We will reach to this case when arr1[i] > arr2[j] and arr2[j] > arr3[k] .It means arr3[k] is smallest. So it cannot be the common element.

Time complexity: O(n)

Auxiliary space: O(1)