Find common elements in three sorted arrays

November 6, 2021

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

#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