In this post we will solve LeetCode 760. Find Anagram Mappings problem using the Java programming language.
You are given two integer arrays nums1 and nums2 where nums2 is an anagram of nums1. Both arrays may contain duplicates. Return an index mapping array mapping from nums1 to nums2 where mapping[i] = j means the ith element in nums1 appears in nums2 at index j. If there are multiple answers, return any of them. An array a is an anagram of an array b means b is made by randomizing the order of the elements in a. Constraints: o 1 <= nums1.length <= 100 o nums2.length == nums1.length o 0 <= nums1[i], nums2[i] <= 10^5 o nums2 is an anagram of nums1. Related Topics: o Array o Hash Table
We are provided with two int[] holding two anagrams. We need to write a function that returns an index mapping array mapping from nums1 to nums2 where mapping[i] = j means the ith element in nums1 appears in nums2 at index j.
If interested in this problem please visit the LeetCode website and get the current requirements and test cases.
Note that the requirements specify that if there are multiple answers we may return any of them. This implies that if characters are repeated we do not need to keep a list of their positions and return multiple arrays.
public int[] anagramMappings(int[] nums1, int[] nums2) {
}
The signature for the function of interest matches nicely the requirements.
I will be solving the problem using the Java programming language and the VSCode IDE on a Windows computer. Because of this, I will need to write some simple test scaffold. The test code IS NOT PART OF THE SOLUTION. The simplest way to solve the problem is to use the online IDE provided by LeetCode.
12,28,46,32,50
50,12,32,46,28
main <<< nums1: [12, 28, 46, 32, 50]
main <<< nums2: [50, 12, 32, 46, 28]
<<< hm: {32=2, 50=0, 12=1, 28=4, 46=3}
main <<< anagramMappings: [1, 4, 3, 2, 0]
84,46
84,46
main <<< nums1: [84, 46]
main <<< nums2: [84, 46]
<<< hm: {84=0, 46=1}
main <<< anagramMappings: [0, 1]
Test cases are separated by two blank lines.
The first two lines in a test case hold the information for the `nums1` and `nums2` arrays respectively. Our test code seems to read the input lines, allocate and populate the int[] arrays and then display them. This is done to make sure all is well so far.
The function of interest is called. The contents of a hashmap is displayed. This is done to make sure the code is working as expected. Such a line IS NOT PART OF THE SOLUTION.
Finally the result returned by the function of interest is displayed.
/**
* Test scaffold.
* !!!! NOT PART OF THE SOLUTION !!!!
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read nums1 array ****
int[] nums1 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read nums2 array ****
int[] nums2 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums1: " + Arrays.toString(nums1));
System.out.println("main <<< nums2: " + Arrays.toString(nums2));
// **** call function of interest and display result ****
System.out.println("main <<< anagramMappings: " + Arrays.toString(anagramMappings(nums1, nums2)));
}The
The test code seems to match closely the description of a test case. I believe there is not much to add to it.
/**
* Return an index mapping array mapping from nums1 to nums2 where
* mapping[i] = j means the ith element in nums1 appears in nums2 at index j.
* If there are multiple answers, return any of them.
*
* Execution: O(n) - Space: O(n)
* Runtime: 1 ms, faster than 87.62% of Java online submissions.
* Memory Usage: 37.8 MB, less than 58.41% of Java online submissions.
*
* 51 / 51 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 37.8 MB
*/
static public int[] anagramMappings(int[] nums1, int[] nums2) {
// **** initialization ****
int[] mappings = new int[nums1.length];
HashMap<Integer, Integer> hm = new HashMap<>();
// **** populate hashmap with contents of nums2 - O(n) ****
for (int i = 0; i < nums2.length; i++)
hm.put(nums2[i], i);
// ???? ????
System.out.println("<<< hm: " + hm.toString());
// **** traverse nums1 populating mappings using the hashmap - O(n) ****
for (int i = 0; i < nums1.length; i++)
mappings[i] = hm.get(nums1[i]);
// **** return mappings array ****
return mappings;
}
We start the function of interest performing an initialization. We create the `mappings` int[] which will hold our solution to be returned by this function. We also create a hashmap which will be used to keep track of the indices of the contents of the array `nums2`.
We then populate the hashmap. Note that we may replace the index if a value appears more than once. This is fine as specified by the requirements.
We then traverse the contents of the `nums1` int[] and populate the `mappings` int[] with the indices of `nums2` int[] held in the hashmap.
The `mappings` int[] is then returned.
Please take a look at the comments section of this function for performance information.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named FindAnagramMappings.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John