Find Anagram Mappings solution and explanation
Google
8 more videos on this problem
Leetcode 760. Find Anagram MappingsAlgorithms Casts · 5:21 · 573 views
Interview Problems - Find Anagram MappingsLeafy C · 8:58 · 537 views
leetcode - 760 Find Anagram MappingslitCode · 6:34 · 333 views
760. Find Anagram Mappings - Week 2/5 Leetcode April ChallengeProgramming Live with Larry · 2:40 · 183 views
Leetcode 760 Find Anagram Mappings - Google Interview Problem Solved In Time Complexity O(N)AlgorithmicIQ · 8:56 · 137 views
Cracking the coding interview with LeetCode Premium for FREE: 760 Find Anagram MappingsSuper Lazy Coder · 9:53 · 65 views
#760. Find Anagram Mappings 寻找异构映射 | leetcode 刷题日记PinkWitch 诸葛筱暖 TV · 3:34 · 50 views
LeetCode 760: Find Anagram Mappings — The HashMap Trick (C#)DSA Mastery Lab · 8:04 · 2 views
LeetCode 760: Find Anagram MappingsAlitaCode · 25:01 · 1 view
The problem
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.
Example 1:
Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28] Output: [1,4,3,2,0] Explanation: As mapping[0] = 1 because the 0th element of nums1 appears at nums2[1], and mapping[1] = 4 because the 1st element of nums1 appears at nums2[4], and so on.
Example 2:
Input: nums1 = [84,46], nums2 = [84,46] Output: [0,1]
Constraints:
1 <= nums1.length <= 100nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 105nums2is an anagram ofnums1.
Approach overview
Problem Overview: You are given two integer arrays nums1 and nums2 where nums2 is an anagram of nums1. The task is to return an array mapping such that mapping[i] is the index j where nums1[i] == nums2[j]. Since the arrays are anagrams, every value in nums1 appears somewhere in nums2.
Approach 1: Brute Force Search (O(n²) time, O(1) space)
The most direct method is to scan nums2 for every element in nums1. For each index i in nums1, iterate through nums2 until you find a matching value and store that index in the result array. This works because the problem guarantees both arrays contain the same multiset of values. The drawback is the nested iteration: each lookup in nums2 may take up to O(n), resulting in overall O(n²) time. Space usage stays O(1) aside from the output array. This approach is acceptable for small inputs but does not scale well.
Approach 2: Hash Table Mapping (O(n) time, O(n) space)
A faster solution uses a hash map to record where each value appears in nums2. First iterate through nums2 and store value → index in a hash table. Then iterate through nums1 and perform constant‑time lookups to retrieve the corresponding index from the map. Each lookup takes O(1) on average, so the entire algorithm runs in O(n) time with O(n) additional space for the map.
Handling duplicates requires a small adjustment. Instead of storing a single index, store a list (or stack) of indices for each value in nums2. When you encounter that value in nums1, pop one index from the list and place it into the result. This guarantees every occurrence is mapped correctly while preserving O(n) complexity.
This solution relies on a hash table for constant‑time lookups, a common pattern in many hash table problems. The iteration over the arrays is straightforward and uses basic array traversal. The key insight is that searching repeatedly is unnecessary when you can precompute the positions once.
Recommended for interviews: The hash table approach is the expected solution. Interviewers want to see that you recognize the repeated lookup pattern and replace it with constant‑time hashing. Mentioning the brute force solution first demonstrates understanding of the problem, while transitioning to the O(n) hash map optimization shows strong problem‑solving instincts.
Solution
We use a hash table d to store each element of the array nums2 and its corresponding index. Then we iterate through the array nums1, and for each element nums1[i], we retrieve its corresponding index from the hash table d and store it in the result array.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the array.
class Solution:
def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]:
d = {x: i for i, x in enumerate(nums2)}
return [d[x] for x in nums1]class Solution {
public int[] anagramMappings(int[] nums1, int[] nums2) {
int n = nums1.length;
Map<Integer, Integer> d = new HashMap<>(n);
for (int i = 0; i < n; ++i) {
d.put(nums2[i], i);
}
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
ans[i] = d.get(nums1[i]);
}
return ans;
}
}class Solution {
public:
vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
unordered_map<int, int> d;
for (int i = 0; i < n; ++i) {
d[nums2[i]] = i;
}
vector<int> ans;
for (int x : nums1) {
ans.push_back(d[x]);
}
return ans;
}
};function anagramMappings(nums1: number[], nums2: number[]): number[] {
const d: Map<number, number> = new Map();
for (let i = 0; i < nums2.length; ++i) {
d.set(nums2[i], i);
}
return nums1.map(num => d.get(num)!);
}func anagramMappings(nums1 []int, nums2 []int) []int {
d := map[int]int{}
for i, x := range nums2 {
d[x] = i
}
ans := make([]int, len(nums1))
for i, x := range nums1 {
ans[i] = d[x]
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Search | O(n²) | O(1) | Useful for understanding the problem or when input size is very small |
| Hash Table Mapping | O(n) | O(n) | General case; optimal approach using constant-time lookups |
Frequently asked questions
Is Find Anagram Mappings easy or hard?
Find Anagram Mappings is classified as an Easy problem. The main concept is recognizing that repeated searches can be replaced with a hash map to achieve linear time.
Find Anagram Mappings Python/Java solution
The typical implementation builds a dictionary or HashMap from nums2 values to indices. Then a second loop over nums1 fills the result array using map lookups. The same logic works in Python, Java, C++, Go, and TypeScript with standard hash map structures.
How to solve Find Anagram Mappings in O(n)?
First build a hash map that stores the indices of every value in nums2. Then iterate through nums1 and look up the corresponding index for each value in the map. If duplicates exist, store lists of indices and pop one when used. Both passes together produce an O(n) solution.
What is the best approach for Find Anagram Mappings?
The best approach uses a hash table to map values in nums2 to their indices. After building the map in one pass, iterate through nums1 and retrieve each index using constant-time lookups. This reduces the complexity to O(n) time with O(n) extra space.
Is Find Anagram Mappings asked at Google/Amazon/Meta?
Find Anagram Mappings is an easy-level interview problem that tests hash table fundamentals and array indexing. Variations of index mapping and hash-based lookups appear frequently in interviews at companies like Amazon and Google.
What data structure is used in Find Anagram Mappings?
A hash table (hash map) is the key data structure. It stores value-to-index mappings from nums2 so that each lookup for nums1 can be done in constant time.
What is the time complexity of Find Anagram Mappings?
The optimal hash table solution runs in O(n) time because each array is traversed once and hash lookups take O(1) on average. The brute force alternative requires O(n²) time since it scans nums2 for every element in nums1.