Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Pseudocode
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
How do you declare an Array in C++?
4.2.
What does time complexity mean?
4.3.
What does space complexity mean?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Find common elements in three sorted arrays

Author Anju Jaiswal
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

This article will look at a problem of common elements in three sorted arrays. Array-based questions are the most popular and vital in coding interviews and programming competitions.

Let's understand the problem statement.

Problem Statement

We have given three sorted arrays of sizes N1, N2, and N3, respectively, and we have to find the common elements in three sorted arrays.

Here first, we will discuss the brute force approach and then the optimized method.

Sample Examples

Example 1:

Input: 
ar1[] = {7, 16, 19, 21, 31} 
ar2[] = {19, 21, 46} 
ar3[] = {2, 5, 8, 19, 20, 21} 

Output: 
20, 80

 

Example 2:

Input: 
ar1[] = {1, 2, 2} 
ar2[] = {2, 2, 6, 7, 10} 
ar3[] = {1, 2, 2, 20} 

Output: 
2, 2

 

Brute Force Approach

The most straightforward approach is to use three for loops to find common elements in three sorted arrays.

  • Using three for loops, produce all possible combinations of triplets (one from each input array) and check if they are equal.
  • This approach is not utilizing the fact that input arrays are sorted.

 

Pseudocode

For i=0, i<= size of array1, i+=1{
    For j = 0, j<= size of array2, j+=1{
          For k =0, k<=size of array3, k+=1{
                  If array[1] and array[2] and array[3] are equal 
                      Then print the element
          }
    }
}

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
void find_Common_Elements(int arr1[], int arr2[], int arr3[], int n1,
                int n2, int n3)
{
    for(int i = 0; i < n1; i++) {
 
        for(int j = 0; j < n2; j++) {
 
            for(int k = 0; k < n3; k++) {
 
                if(arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
                    cout<<(arr1[i])<<" ";
                }
            }
        }
    }
}
// Driver code
int main()
{
    int arr1[] = {7, 16, 19, 21, 31} ;
    int arr2[] = {19, 21, 46} ;
    int arr3[] = {2, 5, 8, 19, 20, 21};

    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
 
    cout << "Common Elements in three sorted arrays are ";
    find_Common_Elements(arr1, arr2, arr3, n1, n2, n3);
    return 0;
} 

 

Output:

Common Elements in three sorted arrays are 19 21

 

Complexity Analysis

Time Complexity: O(n1*n2*n3) 

We are using three loops in this approach; check if all feasible triplet combinations (one from each input array) are equivalent, if they are equal means we find the common elements in three sorted arrays

Space Complexity: O(1) 

No extra space is used.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

In our previous approach, we have found the common elements in three sorted arrays using three for loops. Let's optimize our solution and solve the problem in a single traversal.

The idea here is to traverse all the arrays simultaneously, and if we find the common element, print it.

Pseudocode

  1. Declare three variables (x, y, and z) and set their initial values to zero.
  2. Run a while loop until the array lengths are bigger than the declared variables (size of arr1 > x, size f arr2 >  y, size of arr3 > z).
  3. To locate the common element, compare the values at each stage (arr1[x] == arr2[y] && arr2[y] == arr3[z]). If it is discovered, increase the value of all three variables.
  4. Else increment x if arr1[x] < arr2[y]. Increment y if arr2[y] < arr3[z], else increment z.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

 
// This function prints common elements in ar1
void find_Common_Elements(int arr1[], int arr2[], int arr3[], int n1,
                int n2, int n3)
{
    // Initialize starting indexes for arr1[], arr2[] and
    // arr3[]
    int i = 0, j = 0, k = 0;
 
    // Iterate through three arrays while all arrays have
    // elements
    while (i < n1 && j < n2 && k < n3) {
        // If x = y and y = z, print any of them and move
        // ahead in all arrays
        if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
            cout << arr1[i] << " ";
            i++;
            j++;
            k++;
        }
 
        // x < y
        else if (arr1[i] < arr2[j])
            i++;
 
        // y < z
        else if (arr2[j] < arr3[k])
            j++;
 
        // We reach here when x > y and z < y, i.e., z is
        // smallest
        else
            k++;
    }
}
 

// Driver code
int main()
{
    int arr1[] = {7, 16, 19, 21, 31} ;
    int arr2[] = {19, 21, 46} ;
    int arr3[] = {2, 5, 8, 19, 20, 21};

    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
 
    cout << "Common Elements in three sorted arrays are ";
    find_Common_Elements(arr1, arr2, arr3, n1, n2, n3);
    return 0;
}

 

Output:

Common Elements in three sorted arrays are 19 21

 

Complexity Analysis

Time Complexity: O(n1+n2+n3) 

In this approach to find the common elements in three sorted arrays, we are traversing all the arrays simultaneously, and if we find a common element, print it.

Space Complexity: O(1) 

No extra space is used.

Also see,  Rabin Karp Algorithm

Frequently Asked Questions

How do you declare an Array in C++?

An array is fixed in length i.e static in nature. Array declaration syntax in C/C++:

DataType ArrayName [size];

What does time complexity mean?

The time complexity in computer science is the computational complexity that describes how long it takes a computer to run an algorithm. Choosing the most efficient algorithm is always better when a fundamental problem can be solved using multiple methods.

What does space complexity mean?

An algorithm's amount of memory is known as its space complexity.

Conclusion

This article discussed the different approaches to finding the common elements in three sorted arrays, starting with the brute first approach and the efficient approach with examples and C++ code.

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!