Common Elements

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
15 upvotes
Asked in companies
SAP LabsWalmartFlipkart limited

Problem statement

Given two 1-dimensional arrays containing strings of lowercase alphabets, print the elements that are common in both the arrays i.e. the strings that are present in both the arrays.

Note: 
An element of one array can be mapped only to one element of the array. For example :

Array 1 = {“ab”, “dc”, “ab”, “ab”}
Array 2 = {“dc”, “ab”, “ab”} 

The common elements for the above example will be “dc”, “ab”, and “ab”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case includes two integers, 'N' and 'M', representing the sizes of both the arrays.

The second line of each test case contains 'N' single-spaced strings representing the elements of the first array.

The third line of each test case contains 'M' single-spaced strings representing the elements of the second array.
Output Format: 
For each test case, the common elements of both arrays are printed in the order in which they appear in the second array. The elements are printed in a single space-separated manner. 

The output for each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just return the common elements in the specified order.
Constraints: 
1 <= T <= 10
1 <= N, M <= 10000    
1 <= S <= 10

Where 'T' is the number of test cases. 'N' and 'M' are the sizes of both the arrays and 'S' is the length of the strings of the arrays. Also, the strings contain only lowercase alphabets.

Time limit: 1 sec.
Sample Input 1:
1
3 5
at bat rat
rat bar bat rat to
Sample Output 1:
rat bat
Explanation of the Sample Input 1:
The common elements of both the arrays are “bat” and “rat”. Thus, these two elements are printed in the order in which they appear in the second array.
Sample Input 2:
2
2 2
a b
c d
2 1
coding ninjas
coding
Sample Output 2:
coding
Explanation of Sample Input 2
There are no common elements for the first test case. For the second case, “coding” is the common element.
Hint

For each string in the second array, check if it exists in the first array.

Approaches (3)
Bruteforce approach

The main idea behind this approach is to solve the problem intuitively, and for each string in the second array, check if it exists in the first array (we are checking for each string in the second array because we need the output in the order in which they appear in the second array).
 

Algorithm :
 

  • Start traversing the second array and for each string in the second array, do the following :

    • Loop through the first array and see if the string is present in the first array. If it is present in the first array, add the string to the answer as it is present in both the arrays. Also, in the first array, replace the string with an empty string so that the same string is not considered again in the subsequent iterations.
       
  • The answer will contain the strings in the order in which they appear in the second array. Simply return the answer.
Time Complexity

O(N * M), where ‘N’ and 'M' are the sizes of both the arrays.

 

For each string in the second array, we are traversing the first array. Thus, the final time complexity will be O(N * M).

Space Complexity

O(K), where ‘K’ = min('N', ‘M’) i.e. ‘K’ is the minimum of the sizes of both the arrays.

 

Additional space is used to store the answer i.e. the common strings of both the arrays. The number of common strings of both the arrays would be K = min(N, M) and thus, the final space complexity is O(K).

Code Solution
(100% EXP penalty)
Common Elements
Full screen
Console