Last Updated: 30 Jan, 2021

Common Elements In Three Sorted Arrays

Moderate

Asked in companies

Solve now

Problem statement

You are given three arrays 'A', 'B' and 'C' of length 'N', 'M' and 'K' respectively. All the three arrays are sorted in non-decreasing order. Your task is to find all such elements which are present in all the three given arrays.

Note:

1. The output array should have the same ordering of elements as the original arrays.
2. Even if a particular element appears more than once in each of the three arrays, it should still be present only once in the output array.
3. If there are no common elements in the arrays, return an empty array.

For example:

Consider the three arrays A = [ 2, 3, 4, 7 ] , B = [ 0, 0, 3, 5 ] , C = [ 1, 3, 8, 9 ]
The output array should be [ 3 ] as 3 is the only element which is present in all the three arrays.

Input Format:

The first line of the input contains an integer 'T', denoting the number of test cases. 

The first line of each test case contains three space-separated integers 'N', 'M' and 'K' denoting the number of elements in Array A, Array B and Array C respectively.

The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'A'.

The third line of each test case contains 'M' space-separated integers denoting the elements of the array 'B'.

The fourth line of each test case contains 'K' space-separated integers denoting the elements of the array 'C'.

Output Format:

The only line of output of each test case should contain the elements that are common in all three arrays separated by space.

Print the output of each test case in a new line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N, M, K <= 30000
0 <= A[i] <= 10^9
0 <= B[i] <= 10^9
0 <= C[i] <= 10^9

Where 'A[i]', 'B[i]', 'C[i]' denotes the 'i'th' element of the arrays 'A', 'B' and 'C' respectively.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea is to iterate through one of the three arrays and for each element of the array iterate through the other two arrays and check whether that element is present in the other two arrays. If that element exists in the other two arrays, then we will add it to the output array provided it already does not exist in the output array. At the end we will return the output array.

Note that we can arbitrarily select any of the three arrays as the first array. We are selecting Array A as the first array.

Steps :

Iterate from i = 0 to N-1
- Define two flag variables isPresentInB and isPresentInC. Initialize both of them as 0.
- Iterate from j = 0 to M-1
  - If A[i] equals B[j] then set isPresentInB to 1 and break the loop.
- Iterate from j = 0 to K-1
  - If A[i] equals C[j] then set isPresentInC to 1 and break the loop.
- If both the flag variables isPresentInB and isPresentInC are set to 1, then we will add A[i] to the output array provided it is already not present in it. To check whether an element is already present in the output array we just need to ensure that either the output array is empty or the last element of the output array is not equal to A[i].
  - This idea works because in each iteration we are trying to add an element which is not smaller than any of the output array elements. Therefore we need to compare it with the largest element of the output array i.e. it's last element.
Return the output array.

Solve now

02 Approach

The idea is to optimize the previous approach using Binary Search. This approach is quite similar to the previous approach. The major difference lies in the fact that in the previous approach to check whether any element P is present in Array ARR we were iterating through the whole array whereas in this approach we will use binary search to check whether any element P is present in Array ARR. This idea works because all the arrays are sorted. The advantage of using Binary search is that it optimizes the runtime of the algorithm that checks whether an element P is present in Array ARR from Linear Time Complexity to Logarithmic Time Complexity.

Let BinarySearch ( ARR, P ) be a function that returns True when element P exists in Array ARR. Otherwise it returns False.

Steps :

Iterate from i = 0 to N-1
- Define two flag variables isPresentInB and isPresentInC.
- If BinarySearch (B, A[i]) returns True then set isPresentInB to 1. Otherwise set isPresentInB to 0.
- If BinarySearch (C, A[i]) returns True then set isPresentInC to 1. Otherwise set isPresentInC to 0.
- If both the flag variables isPresentInB and isPresentInC are set to 1, then we will add A[i] to the output array provided it is already not present in it. To check whether an element is already present in the output array we just need to ensure that either the output array is empty or the last element of the output array is not equal to A[i].
  - This idea works because in each iteration we are trying to add an element which is not smaller than any of the output array elements. Therefore we need to compare it with the largest element of the output array i.e. it's last element.
Return the output array.

Solve now

03 Approach

The idea is to maintain three pointers one for each array. Let the pointer to Array A be p, pointer to Array B be q and pointer to Array C be r with all three of them initialized to 0. In each iteration we first get the element which is currently been pointed by first pointer i.e. A[p] and then we move the pointers to the other two arrays ahead while the element pointed by them is smaller than A[p]. Then we check whether the three elements i.e. A[p], B[q] and C[r] contain the same value.If yes, then we add that value to the output array provided it already does not exist in it and move the first pointer forward.

Steps:

Define three pointer variables p,q and r and initialize all three of them as 0.
While p is less than N, then
- While q is less than M and B[q] is less than A[p], then
  - Increase q by 1.
- While r is less than K and C[r] is less than A[p], then
  - Increase r by 1.
- If either q equals M or r equal K then we will break the loop as we have already traversed one of the arrays completely and now no more new common elements can be present.
- If A[p] equals both B[q] and C[r] then we will add A[p] to the output array provided it is already not present in it.To check whether an element is already present in the output array we just need to ensure that either the output array is empty or the last element of the output array is not equal to the current element.
  - This idea works because in each iteration we are trying to add an element which is not smaller than any of the output array elements. Therefore we need to compare it with the largest element of the output array i.e. it's last element.
- Increase p by 1.
Return the output array.

Solve now