Find all Common Elements in Given Three Sorted Arrays

Problem Statement

In find all common elements in given three sorted arrays problem, we have given three sorted arrays and you have to find common numbers that is present in all three arrays.

Example

Input:

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

Explanation

Here we have given sorted array and we need to find the common elements in all arrays. We take three-pointers that denote the beginning index of the arrays. Now check the condition that if any element is less than with respect to others then increase that pointer value and not that pointer denotes to the next element. Moving like that till the end where we reach at the end on any array. If we hit the end of an array then stop the iteration and print the result. Now for solid understanding check the below algorithm.

Algorithm for find Common Elements

1. Take three-pointers like variables i, j, and k pointing to the starting index of the three arrays respectively.

2. Check if the three numbers pointed by the variables are same or not

3. If same then print the value and increment all the three variables hence moving forward in the respective arrays.

4. Else increment the variable which is pointing to the smaller ones.

5. If an array gets traversed completely then we check for the remaining two arrays plainly.

6. If two arrays are traversed then simply print the untraversed part of the third array because we know that it is already sorted.

Implementation

C++ Program for find Common Elements

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int arr1[] = {2, 8, 15 , 20, 35, 45, 100};
  int arr2[] = {5, 9, 20, 45, 110};
      int arr3[] = {3, 4, 15, 20, 30, 45, 80, 120};
      int n1 = sizeof(arr1)/sizeof(arr1[0]);
      int n2 = sizeof(arr2)/sizeof(arr2[0]);
      int n3 = sizeof(arr3)/sizeof(arr3[0]);
  
  
  int  i = 0 ,  j = 0 , k = 0; // i ,j and k are pointing at the  start of 1st , 2nd and 3rd array resepectively.
  
  while(i < n1 and j < n2 and k < n3)
  {
    if(arr1[i] == arr2[j] and arr3[k] == arr1[i]) //if all elements are same then
    {
      cout << arr1[i] <<" ";
      i++; j++; k++;
    }
    //increase the array index variable of those which are small
    else if(arr1[i] < arr2[j])
      i++;
    else if(arr2[j] < arr3[k])
      j++;
    else
      k++;
    
  }
  return 0;
}

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n1 = sr.nextInt();
        int n2 = sr.nextInt();
        int n3 = sr.nextInt();
        int a[] = new int[n1];
        int b[] = new int[n2];
        int c[] = new int[n3];
        for(int i=0;i<n1;i++)
        {
            a[i] = sr.nextInt();
        }
        for(int i=0;i<n2;i++)
        {
            b[i] = sr.nextInt();
        }
        for(int i=0;i<n3;i++)
        {
            c[i] = sr.nextInt();
        }
        int  i = 0 ,  j = 0 , k = 0; // i ,j and k are pointing at the  start of 1st , 2nd and 3rd array resepectively.
        while((i < n1) && ((j < n2) && (k < n3)))
        {
          if(a[i] == b[j] && c[k] == a[i]) //if all elements are same then
          {
            System.out.print(a[i]+" ");
            i++; j++; k++;
          }
          //increase the array index variable of those which are small
          else if(a[i] < b[j])
            i++;
          else if(b[j] < c[k])
            j++;
          else
            k++;
        }
    }
}

7 5 8
2 8 15 20 35 45 100
5 9 20 45 110
3 4 15 20 30 45 80 120

20 45