Find common elements in three sorted arrays

October 18, 2024

Find common elements in three sorted arrays

In the Find common elements in three sorted arrays problem, we have to print the elements which are present in all the three arrays given to us. It is a famous interview problem asked in many interviews. In this article, we will provide a C++ solution with an explanation.

Find common elements in three sorted arrays Problem Description

Find the common elements Problem Description

Given three sorted arrays output all elements present in all three arrays.

Input:

  • Three arrays of different sizes.

Output:

  • Integers present in all three arrays separated by single space.

Find the common elements Problem Solution

Brute Force

The idea here is to use three nested loops all loop through all elements. If we arrive same value elements we simply print those.

Time Complexity – O(n1*n2*n3) where n1,n2 & n3 are array sizes.

Space Complexity – O(1)

Optimized Approach

The idea here is to use sorted nature of the arrays to our advantage. We create three pointers i, j & k . Each of these point to start of an array. We move these pointers according to the following conditions –

  • If value of element at i,j & k are equal simple print the element and increment all three pointers.
  • If the value is not equal move increment the pointer pointing to the minimum element.
  • Repeat above steps till any one pointer reaches the end.

Time Complexity – O(max(n1,n2,n3)) O(n1*n2*n3) where n1,n2 & n3 are array sizes.

Space Complexity – O(1)

Find common elements in three sorted arrays Algorithm Steps

Code

Run 
#include <bits/stdc++.h>
using namespace std;
void commonElements(int A[], int B[], int C[], int na, int nb, int nc)
{
    int i = 0, j = 0, k = 0;

    while (i < na && j < nb && k < nc)
    {
        if (A[i] == B[j] && B[j] == C[k])
        {
            cout << A[i] << ” “;
            i++;
            j++;
            k++;
        }
        else
        {
            if (A[i] <= B[j] && A[i] <= C[k])
                i++;
            else if (B[j] <= A[i] && B[j] <= C[k])
                j++;
            else if (C[k] <= A[i] && C[k] <= B[j])
                k++;
        }
    }
}
int main()
{
    int A[] = {1, 2, 3, 5, 8};
    int B[] = {1, 3, 8, 9};
    int C[] = {3, 8, 10};

    commonElements(A, B, C, 5, 4, 3);
    return 0;
}

Output

3 8

11 comments on “Find common elements in three sorted arrays”


  • doddianil909

    //finding three comman elements in array
    import java.util.*;

    class test {
    public static void main(String… args) {
    int n, i, j, k = 0,l=0, count,count1;
    System.out.println(“Enter the size of the array:”);
    Scanner s = new Scanner(System.in);
    n = s.nextInt();

    int a1[] = new int[n];
    int a2[] = new int[n];
    int a3[]=new int[n];
    int a4[] = new int[n]; // Array to store common elements
    int a5[]=new int[n];
    System.out.println(“Enter first array elements:”);
    for (i = 0; i < n; i++) {
    a1[i] = s.nextInt();
    }

    System.out.println("Enter second array elements:");
    for (i = 0; i < n; i++) {
    a2[i] = s.nextInt();
    }

    System.out.println("Enter third array elements:");
    for (i = 0; i < n; i++) {
    a3[i] = s.nextInt();
    }
    for(i=0;i<n;i++)
    {
    count=0;
    for(j=0;j<n;j++)
    {
    if(a1[i]==a2[j])
    {
    count++;
    }
    }
    if(count!=0)
    {
    a4[k]=a1[i];
    k++;
    }
    }
    for(i=0;i<k;i++)
    {
    count1=0;
    for(j=0;j<n;j++)
    {
    if(a4[i]==a3[j])
    {
    count1++;
    }
    }
    if(count1!=0)
    {
    a5[k]=a4[i];
    l++;
    }
    }

    if(l!=0)
    {
    System.out.println("Common elements are:");
    for (i = 0; i < k; i++) {
    System.out.println(a4[i]);
    }
    }
    else
    {
    System.out.println("there is no common elements in arrays");
    }

    }
    }
    this is code in java


  • MD

    //Finding common elemments in three arrays

    public class Problem1 {
    public static void main(String[] args) {
    int arr1[]= {1,2,3};
    int arr2[]={2,3,4};
    int arr3[]={3,4,5};
    find(arr1, arr2, arr3);
    }

    static void find(int[] arr1, int[] arr2, int[] arr3) {
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < arr1.length && j < arr2.length && k < arr3.length) {
    if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
    System.out.println(arr1[i]);
    i++;
    j++;
    k++;
    }
    else if (arr1[i]<arr2[j]) {
    i++;
    }
    else if(arr2[j]<arr3[k]){
    j++;
    }
    else{
    k++;
    }
    }
    }

    }


  • KANAKA

    # Function to find the intersection of two arrays

    def find_intersection(arr1, arr2, temp, m, n, k):

    i = 0

    j = 0

    while i < m and j < n:

    if arr1[i] < arr2[j]:

    i += 1

    elif arr2[j] < arr1[i]:

    j += 1

    else:

    temp[k[0]] = arr1[i]

    i += 1

    j += 1

    k[0] += 1

    # Main function

    def main():

    arr1 = [1, 5, 10, 20, 40, 80]

    arr2 = [6, 7, 20, 80, 100]

    arr3 = [3, 4, 15, 20, 30, 70, 80, 120]

    n1 = len(arr1)

    n2 = len(arr2)

    n3 = len(arr3)

    temp = [0] * 200000

    ans = [0] * 200000

    k = [0] # Mutable list to simulate pass-by-reference

    # Function call to find the temp array

    find_intersection(arr1, arr2, temp, n1, n2, k)

    temp_size = k[0]

    k[0] = 0

    # Function call to find the ans array

    find_intersection(arr3, temp, ans, n3, temp_size, k)

    print("Common elements present in arrays are:")

    # Printing the common elements

    for i in range(k[0]):

    print(ans[i], end=" ")

    print()

    if __name__ == "__main__":

    main()


  • Avothu Sharath

    a = sorted(list(map(int,input(“Enter first array: “).split())))
    b = sorted(list(map(int,input(“Enter second array: “).split())))
    c = sorted(list(map(int,input(“Enter third array: “).split())))
    d = set(a+b+c)
    print(d)
    n = []
    for i in range(len(d)):
    if i in a and i in b and i in c:
    n.append(i)
    print(n)


  • Rudransh

    a=[1,2,3,5,8,9]
    b=[1,3,8,9]
    c=[3,8,10,9]
    l=[]
    for i in a:

    if i in b and i in c:
    l.append(i)

    print(l)


    • doddianil909

      import java.util.*;

      class test {
      public static void main(String… args) {
      int n, i, j, k = 0, count,count1;
      System.out.println(“Enter the size of the array:”);
      Scanner s = new Scanner(System.in);
      n = s.nextInt();

      int a1[] = new int[n];
      int a2[] = new int[n];
      int a3[]=new int[n];
      int a4[] = new int[n]; // Array to store common elements

      System.out.println(“Enter first array elements:”);
      for (i = 0; i < n; i++) {
      a1[i] = s.nextInt();
      }

      System.out.println("Enter second array elements:");
      for (i = 0; i < n; i++) {
      a2[i] = s.nextInt();
      }

      System.out.println("Enter third array elements:");
      for (i = 0; i < n; i++) {
      a3[i] = s.nextInt();
      }

      for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++) {
      if (a1[i] == a2[j]) {
      count = 0; // Reset count for each new element comparison
      for (int l = 0; l < k; l++) {
      if (a4[l] == a1[i]) {
      count++; // Increment count if element is found in a4
      }
      }
      if (count == 0) { // If no duplicates are found
      a4[k] = a1[i];
      k++;
      }
      //break; // Break to avoid counting the same element multiple times
      }
      }
      }
      for(i=0;i<k;i++)
      {
      count1=0;
      for(j=0;j<n;j++)
      {
      if(a4[i]==a3[j])
      {
      count1++;
      }
      }
      if(count1==0)
      {
      a4[k]=a3[j];
      k++;
      }
      }

      if(k!=0)
      {
      System.out.println("Common elements are:");
      for (i = 0; i < k; i++) {
      System.out.println(a4[i]);
      }
      }
      else
      {
      System.out.println("there is no common elements in arrays");
      }

      }
      }
      the code in java