Anagram Mapping

Easy
0/40
profile
Contributed by
27 upvotes

Problem statement

You are given two arrays ‘A’ and ‘B’, each containing ‘N’ distinct integers. You are also given that ‘B’ is an anagram of ‘A’

Find the index mapping from array ‘A’ to array ‘B’, ie: for each element in ‘A’ you need to find the index in ‘B’ corresponding to that element.

An array ‘B’ is an anagram of an array ‘A’ means ‘B’ is made by randomizing the order of the elements in ‘A’.

For Example : 
If ‘N’ = 5, ‘A’ = {10, 20, 30, 40, 50} and ‘B’ = {20, 10, 40, 50, 30}

Then we will print {1, 0, 4, 2, 3} because:

A[0] occurs at 1st index in array B, A[1] occurs at 0th index, A[2] occurs at 4th index, A[3] occurs at 2nd index, A[4] occurs at 3rd index.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’, denoting the number of elements in the array.

The second line of each test case contains N distinct integers ‘A’, denoting the array elements of the first array.

The third line of each test case contains N distinct integers ‘B’, denoting the array elements of the second array.
Output Format : 
For each test case, print the index mapping for the two anagram arrays.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10      
1 ≤ N ≤ 10000
-10^9 ≤ A[i], B[i] ≤ 10^9

Time limit: 1 sec
Sample Input 1 :
2
5
10 20 30 40 50
20 10 40 50 30
5
10 20 30 40 50
10 20 30 40 50
Sample Output 1 :
1 0 4 2 3
0 1 2 3 4
Explanation For Sample Input 1 :
For test case 1 :
We will print {1, 0, 4, 2, 3} because:
A[0] occurs at 1st index in array B, A[1] occurs at 0th index, A[2] occurs at 4th index, A[3] occurs at 2nd index, A[4] occurs at 3rd index. 

For test case 2 : 
We will print {0, 1, 2, 3, 4} because:
Array ‘A’ is the same as array ‘B’, as they both have the same ordering of elements.
Sample Input 2 :
2
3
1 2 3
3 2 1
3
1 2 3
3 1 2
Sample Output 2 :
2 1 0
1 2 0
Hint

Store the information for the elements of array ‘B’ in a hash-map.

Approaches (1)
Hash-Map

This is quite an easy problem. All we need to do is to store the elements of array ‘B’ in a hash-map so that the index corresponds to each element is stored in it. Now we can simply iterate through each element in array ‘A’, and find the index corresponding to that element in the hash-map. Here we won’t have to make any additional checks, this is because we are given that both the input arrays are anagrams, so checking for the elements existing in the hash-map will not necessarily be required.

 

The steps are as follows :

  1. Initialize a hash-map ‘elementIndex’.
  2. Declare an array ‘mapping’, this will store the final answer to be returned.
  3. Iterate through each element in ‘B’, and insert each one into the hash-map with its corresponding index.
  4. Now, iterate each element in ‘A’, and find the value corresponding to that element in the hash-map, as the value in the hash-map stores the information about the index, therefore insert it in the ‘mapping’ array.
  5. Finally, return the ‘mapping’ array.
Time Complexity

O( N ), where N denotes the size of the array.

 

We iterate through each element in both ‘A’ and ‘B’ exactly once.

Hence the time complexity is O( N ).

Space Complexity

O( N ), where N denotes the size of the array.

 

Extra space is used to store the information about the index corresponding to each element in array B.

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Anagram Mapping
Full screen
Console