Last Updated: 23 Oct, 2020
Common Elements
Moderate
Asked in companies
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”.
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.
Approaches
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.
- 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.
The main idea behind this approach is to use a hashmap to store the count of the strings.
Algorithm :
- Traverse the first array and for every string in the first array do the following :
- If the string is not already present in the hashmap, insert it in the hashmap with a count of 1.
- Else increment the count of the string in the hashmap by 1.
- Now, traverse the second array and for every string do the following :
- If the string is present in the hashmap, this string is a common element of both the arrays. Add this string to the answer and decrement its count in the hashmap.
Now, if the count becomes 0, this means that all the instances of the current string in the first array have been considered. So, delete this string from the hash map.
- If the string is not present in the hashmap, then this string is not present in the first array and will not be a part of the answer.
- If the string is present in the hashmap, this string is a common element of both the arrays. Add this string to the answer and decrement its count in the hashmap.
- After both the traversals, the answer will have the common strings in the order in which they appear in the second array. Thus, we need to simply return the answer.
The main idea behind this approach is to use a trie to store the frequencies of the strings in the first array. We can add an additional field “COUNT” in the implementation of the node of the trie. This field will be equal to the number / occurrences of the current string in the first array. For the nodes that do not represent the end of a string, the value of count will be zero.
Firstly, we traverse the first array and insert the strings in a trie. While inserting a string in the trie, we increment the variable “COUNT” of the last node i.e. the node representing the last character of the string.
After the creation of the trie, we traverse the second array and for each string in the second array, we check if it is present in the trie. If the string exists in the trie, we add it to the answer and decrement the variable “COUNT” for the last node i.e. the node representing the last character of the string.
After the traversal of the second array, the answer will contain the common strings.