Common Elements In Three Sorted Arrays

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
55 upvotes
Asked in companies
MicrosoftTech MahindraOptum

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
4 3 3
1 4 5 6
3 4 5 
5 6 7
3 1 3
4 6 8
6
2 2 6

Sample Output 1:

5
6

Explanation for Sample Input 1:

For the first test case : 
Elements that are common in array A and B = [ 4, 5 ]. Out of which only 5 is present in Array C. Therefore the output array is [ 5 ] in this case.

For the second test case : 
It can be seen that only 6 is present in all the three arrays. Therefore the output array is [ 6 ] in this case.

Sample Input 2:

2
4 4 3
1 2 2 3
2 2 3 3
2 2 3
3 2 2
1 2 3
0 6
4 6

Sample Output 2:

2 3

Explanation for Sample Input 2:

For the first test case, elements 2,3 are present in all three arrays.
For the second test case, no element is common in all three arrays, hence we do not print anything.
Hint

Iterate through one array and for each element try to check whether it is present in the other two arrays.

Approaches (3)
Brute force 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 :

  1. 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.
  2. Return the output array.

 

Time Complexity

O(N*(M+K)), where N, M and K are the number of elements in Arrays A, B and C respectively. 

 

In the worst case, when none of the elements of Array A are present in both Array B and Array C we will need to execute (M+K) iterations for each of the N elements of Array A. Hence, the overall Time Complexity is O(N*(M+K)).

Space Complexity

O(1), as we are using constant extra memory.

Code Solution
(100% EXP penalty)
Common Elements In Three Sorted Arrays
Full screen
Console