💬 Discord
Sign In
NeetCode #11LC-760EasyArrays & HashingNC Algo100
← Back to All Problems

#11 · #760 · Find Anagram Mappings(找出变位映射)

📌 Problem Statement & Constraints

Given two arrays nums1 and nums2 that are anagrams of each other, return a mapping array mapping where mapping[i] == j means nums2[j] == nums1[i]. If there are multiple answers, return any of them. Constraints: 1 <= nums1.length == nums2.length <= 100, 0 <= nums1[i], nums2[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. For each value in nums1, we need some index in nums2 holding that value. Since values may repeat, store a list of indices per value.
  2. Build a map from value to the list of positions where it occurs in nums2.
  3. Walk nums1 in order and consume one position from the corresponding list each time.
  4. A per-value cursor ensures each occurrence in nums1 maps to a distinct occurrence in nums2, which is what the problem requires.

💻 Benchmark Python3 Implementation

class Solution:
    def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]:
        from collections import defaultdict
        pos = defaultdict(list)
        for j, v in enumerate(nums2):
            pos[v].append(j)               # all positions of each value
        used = defaultdict(int)            # how many we have consumed so far
        res = []
        for v in nums1:
            res.append(pos[v][used[v]])    # take the next unused position
            used[v] += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to index nums2, one pass over nums1.
💾 Space Complexity
O(n) for the position lists.

⚠️ Interview Pitfalls & Follow-ups

  • Using a plain value-to-index dict: duplicates in nums2 would overwrite each other, and two equal values in nums1 would map to the same index, which the problem forbids.
  • Assuming the mapping is unique: the problem explicitly allows any valid answer, so do not try to compute a canonical one.
  • Sorting both arrays and mapping by rank: it works, but O(n log n) and more code than the direct index lists.