760. Find Anagram Mappings
Problem Description
In this problem, you have two integer arrays, nums1
and nums2
. The array nums2
is an anagram of nums1
, meaning nums2
contains all the elements of nums1
, possibly in a different order, and both arrays may have repeated numbers. The goal is to create a mapping from nums1
to nums2
in such a way that for each index i
in nums1
, mapping[i]
gives you the index j
in nums2
where the i
-th element of nums1
is located. Since nums2
is an anagram of nums1
, there is always at least one index j
in nums2
for every element in nums1
.
Your task is to return any one of these index mapping arrays, as there may be multiple valid mappings due to duplicates.
Intuition
The intuition behind the solution involves two key observations:
- Since
nums1
andnums2
are anagrams with possible duplicates, the elements innums1
will surely be found innums2
. - There can be multiple positions for a single element of
nums1
innums2
due to duplicates.
The approach uses a dictionary data structure to keep track of the indices of elements in nums2
. A Python defaultdict
is used here with a set as the default data type to handle multiple indices for duplicates in an efficient way. We iterate over nums2
and fill the dictionary such that each unique number in nums2
is a key, and the corresponding value is a set of indices where this number appears in nums2
.
After we have this dictionary ready, we iterate over nums1
and for each element, we pop
an index from the set in the dictionary. This works well because we can remove any index from the set (since any mapping is valid), and we are guaranteed to have at least one index in the set for each element due to the anagram property. The result is an index mapping list that satisfies the problem requirement.
Solution Approach
Let's dive into the implementation details of the given solution:
-
Data Structures Used:
defaultdict
from Collections module: A dictionary subclass that calls a factory function to supply missing values. In this case, the factory function isset
which holds indices.set
: A built-in Python data structure used here to store indices of the elements innums2
. Sets are chosen because they allow efficient addition and removal of elements, and we don't care about the order of indices.
-
Algorithm Steps:
- Initialize a
defaultdict
withset
as the default factory function:mapper = defaultdict(set)
. - Enumerate over
nums2
and fill themapper
: For eachnum
encountered at indexi
innums2
, add indexi
to the set corresponding tonum
in themapper
. This essentially records the indices where each number fromnums1
can map to innums2
. - Generate the Index Mapping Array: Iterate over
nums1
, and for eachnum
,pop
a value from the set corresponding tonum
in themapper
. This value is an index innums2
wherenum
occurs.pop
is used because it removes an element from the set, ensuring that an index is not used twice. The index is appended to the resulting list.
- Initialize a
-
Complexity Analysis:
- Time Complexity:
O(N)
whereN
is the number of elements innums1
(ornums2
, since they have the same length). It'sO(N)
because we do a single pass over bothnums1
andnums2
. - Space Complexity:
O(N)
for themapper
, as it stores indices for elements innums2
. In the worst case, where all elements innums2
are distinct, themapper
will store one index for each element.
- Time Complexity:
The pattern used in this solution can be identified as Hash Mapping. It utilizes the constant time access feature of the dictionary (hash map
) for storing and retrieving element indices.
By following these steps, the function anagramMappings(nums1, nums2)
will return the index mapping list that will form a correct anagram mapping from nums1
to nums2
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Consider the following small example to illustrate the solution approach:
Let nums1
be [12, 28, 46, 32, 50]
and nums2
be [50, 12, 32, 46, 28]
.
Firstly, we'll initialize our mapper
as a defaultdict
of sets. It will look like this after we process nums2
:
50
appears at index0
innums2
12
appears at index1
innums2
32
appears at index2
innums2
46
appears at index3
innums2
28
appears at index4
innums2
So, our mapper
would be filled as follows:
1mapper = { 2 50: {0}, 3 12: {1}, 4 32: {2}, 5 46: {3}, 6 28: {4} 7}
Next, we iterate over nums1
:
- For
12
, wepop
an index frommapper[12]
, which gives us1
. Nowmapper[12]
is empty. - For
28
, wepop
an index frommapper[28]
, which gives us4
andmapper[28]
becomes empty. - For
46
, wepop
an index frommapper[46]
, which is3
andmapper[46]
is now empty. - For
32
, wepop
frommapper[32]
giving us2
andmapper[32]
is emptied. - Finally for
50
,pop
frommapper[50]
gives us0
and emptiesmapper[50]
.
The resulting index mapping array would be [1, 4, 3, 2, 0]
which is a valid anagram mapping from nums1
to nums2
since if we position the elements of nums1
using these indices in nums2
, we get the same list as nums1
.
To summarize, the resulting mapping array is built by popping an index from the set of indices associated with each corresponding element in nums1
from our mapper
dictionary. This process ensures that each element from nums1
is uniquely matched to an element in nums2
, following the stipulation of the anagram relationship between the two arrays.
Solution Implementation
1from collections import defaultdict
2from typing import List
3
4class Solution:
5 def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]:
6 # Dictionary to store the mapping of each number in nums2 to its indices
7 index_mapper = defaultdict(set)
8
9 # Populate the index_mapper with elements of nums2 and their respective indices
10 for index, number in enumerate(nums2):
11 index_mapper[number].add(index)
12
13 # Create the result list by mapping each number in nums1 to an index in nums2
14 # The pop method is used to ensure the same index is not reused
15 result = [index_mapper[number].pop() for number in nums1]
16
17 return result
18
1class Solution {
2 // Function to find an anagram mapping from nums1 to nums2.
3 public int[] anagramMappings(int[] nums1, int[] nums2) {
4 // Create a map to hold the indices of each number in nums2.
5 Map<Integer, Set<Integer>> numIndicesMap = new HashMap<>();
6 // Fill the map: number -> its indices in nums2.
7 for (int i = 0; i < nums2.length; ++i) {
8 // If the key is not already in the map, put it with a new empty set.
9 // Then add the current index to the set of indices.
10 numIndicesMap.computeIfAbsent(nums2[i], k -> new HashSet<>()).add(i);
11 }
12
13 // Initialize the result array that will hold the mappings.
14 int[] result = new int[nums1.length];
15 // Find the anagram mappings from nums1 to nums2.
16 for (int i = 0; i < nums1.length; ++i) {
17 // Get the set of indices for the current number from nums1 in nums2.
18 Set<Integer> indicesSet = numIndicesMap.get(nums1[i]);
19 // Get and use the next available index (iterator's next).
20 int index = indicesSet.iterator().next();
21 // Save the index in the result array.
22 result[i] = index;
23 // Remove the used index to ensure one-to-one mapping.
24 indicesSet.remove(index);
25 }
26 // Return the completed result array.
27 return result;
28 }
29}
30
1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4
5class Solution {
6public:
7 // Function to find an anagram mapping from nums1 to nums2.
8 std::vector<int> anagramMappings(std::vector<int>& nums1, std::vector<int>& nums2) {
9 // Create a map to hold the indices of each number in nums2.
10 std::unordered_map<int, std::unordered_set<int>> numIndicesMap;
11 // Fill the map: number -> its indices in nums2.
12 for (int i = 0; i < nums2.size(); ++i) {
13 // Add the current index to the set of indices for the number in nums2.
14 numIndicesMap[nums2[i]].insert(i);
15 }
16
17 // Initialize the result vector that will hold the mappings.
18 std::vector<int> result(nums1.size());
19 // Find the anagram mappings from nums1 to nums2.
20 for (int i = 0; i < nums1.size(); ++i) {
21 // Get the set of indices for the current number from nums1 in nums2.
22 std::unordered_set<int>& indicesSet = numIndicesMap[nums1[i]];
23 // Get and use the next available index from the set.
24 auto it = indicesSet.begin();
25 int index = *it;
26 // Save the index in the result vector.
27 result[i] = index;
28 // Remove the used index to ensure one-to-one mapping.
29 indicesSet.erase(it);
30 }
31 // Return the completed result vector.
32 return result;
33 }
34};
35
1// Define a function to find an anagram mapping from nums1 to nums2.
2function anagramMappings(nums1: number[], nums2: number[]): number[] {
3 // Create a map to hold indices for each number in nums2.
4 const numIndicesMap: Map<number, Set<number>> = new Map();
5
6 // Fill the map with number -> its indices in nums2.
7 nums2.forEach((num, index) => {
8 const indicesSet = numIndicesMap.get(num) || new Set<number>();
9 indicesSet.add(index);
10 numIndicesMap.set(num, indicesSet);
11 });
12
13 // Initialize the result array to hold the mappings.
14 const result: number[] = new Array(nums1.length);
15
16 // Find the anagram mappings from nums1 to nums2.
17 nums1.forEach((num, i) => {
18 // Get the set of indices for the current number from nums1 in nums2.
19 const indicesSet = numIndicesMap.get(num);
20 if (!indicesSet) {
21 throw new Error('No index found for number ' + num);
22 }
23
24 // Get and use the next available index.
25 const index = indicesSet.values().next().value;
26 // Save the index in the result array.
27 result[i] = index;
28 // Remove the used index to ensure one-to-one mapping.
29 indicesSet.delete(index);
30 });
31
32 // Return the completed result array.
33 return result;
34}
35
36// Example usage of the function
37const nums1 = [12, 28, 46, 32, 50];
38const nums2 = [50, 12, 32, 46, 28];
39const mapping = anagramMappings(nums1, nums2); // Should produce the anagram mapping of nums1 to nums2.
40
Time and Space Complexity
The given Python function anagramMappings
finds an index mapping from nums1
to nums2
, indicating where each number in nums1
appears in nums2
. Here is the complexity analysis:
Time Complexity:
The function consists of two main parts: building the mapper
dictionary and constructing the result list.
-
Constructing
mapper
: We iterate throughnums2
once to build themapper
dictionary. For each element innums2
of sizen
, inserting into a set in the dictionary takes amortized O(1) time. Thus, this part has a time complexity of O(n). -
Constructing the result list: For each element in
nums1
, which also can be sizen
in the worst case, we pop an element from the corresponding set inmapper
. Each pop operation takes O(1) time because it removes an arbitrary element from the set. Thus, this part also has a time complexity of O(n).
The total time complexity of the function is O(n) + O(n) = O(n), where n
is the length of nums2
.
Space Complexity:
-
The space used by
mapper
: In the worst case, if all elements innums2
are unique, the dictionary will containn
sets, each with a single index. So, the space complexity formapper
will be O(n). -
The space for the result list: A new list of the same size as
nums1
is created for the output. Sincenums1
andnums2
can be of sizen
, this list will also have a space complexity of O(n).
The total space complexity of the function is O(n) [for mapper
] + O(n) [for the result list] = O(2n), which simplifies to O(n), where n
is the length of nums2
.
Note: The space complexity only considers additional space used by the program, not the input and output space. If we consider the inputs and outputs, the space complexity would technically be O(n + n + n), which still simplifies to O(n).
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time