Problem Description

You are given two integer arrays nums1 and nums2, where nums2 is an anagram of nums1. This means nums2 contains exactly the same elements as nums1, but potentially in a different order. Both arrays may contain duplicate values.

Your task is to create an index mapping array called mapping that shows where each element from nums1 appears in nums2. Specifically, mapping[i] = j means that the element at position i in nums1 can be found at position j in nums2.

For example:

• If nums1 = [12, 28, 46, 32, 50] and nums2 = [50, 12, 32, 46, 28]
• The output could be [1, 4, 3, 2, 0] because:
  • nums1[0] = 12 appears at nums2[1], so mapping[0] = 1
  • nums1[1] = 28 appears at nums2[4], so mapping[1] = 4
  • nums1[2] = 46 appears at nums2[3], so mapping[2] = 3
  • And so on...

When there are duplicate elements in the arrays, each element in nums1 should be mapped to one of its occurrences in nums2. Any valid mapping is acceptable - you don't need to find a specific one.

The solution uses a hash map to store all indices where each value appears in nums2, then for each element in nums1, it retrieves and uses one of those indices from the hash map.

Intuition

Since we need to find where each element from nums1 appears in nums2, the most straightforward approach is to first record all positions of each element in nums2. This way, when we iterate through nums1, we can quickly look up where each element exists in nums2.

The key insight is that we're essentially solving a lookup problem - for each element in nums1, we need to find its position in nums2. Rather than searching through nums2 every time we need to find an element (which would be inefficient with O(n²) time complexity), we can preprocess nums2 once to build a mapping of values to their indices.

Why use a set for storing indices? Since the arrays are anagrams, every element in nums1 is guaranteed to exist in nums2. When duplicates exist, a single value might appear at multiple indices in nums2. Using a set allows us to store all possible indices for each value, and then we can simply pop() one index when we need it. The pop() operation ensures that each index in nums2 is used only once, maintaining a valid one-to-one mapping.

The beauty of this approach is that it handles duplicates naturally - if a value appears multiple times in both arrays, we store all its positions from nums2 and consume them one by one as we encounter the same value in nums1. Since both arrays are anagrams, we're guaranteed to have exactly the right number of indices for each value.

Solution Approach

The implementation uses a hash map with sets to efficiently solve this problem:

1. Build the index map from nums2:

   • Create a defaultdict(set) called mapper to store value-to-indices mappings
   • Iterate through nums2 with enumeration to get both index i and value num
   • For each element, add its index to the set of indices for that value: mapper[num].add(i)
   • This handles duplicates by storing all indices where each value appears

2. Create the mapping array:

   • Use a list comprehension to iterate through each element in nums1
   • For each element num in nums1, access mapper[num] to get the set of available indices
   • Use pop() to remove and return one index from the set
   • This ensures each index from nums2 is used exactly once

Why this works:

• Since nums2 is an anagram of nums1, every element in nums1 is guaranteed to exist in nums2 with the same frequency
• The pop() operation removes an arbitrary element from the set, which satisfies the requirement that "any valid mapping" is acceptable
• Time complexity: O(n) where n is the length of the arrays - we iterate through nums2 once to build the map, then through nums1 once to build the result
• Space complexity: O(n) for storing the hash map and the result array

The algorithm elegantly handles all cases including duplicates, as the set automatically manages multiple occurrences of the same value, and we consume indices one at a time as needed.

Example Walkthrough

Let's walk through a small example with duplicates to illustrate the solution approach.

Given:

• nums1 = [4, 2, 4, 3]
• nums2 = [3, 4, 2, 4]

Step 1: Build the index map from nums2

We iterate through nums2 and record where each value appears:

• Index 0: value = 3 → mapper[3] = {0}
• Index 1: value = 4 → mapper[4] = {1}
• Index 2: value = 2 → mapper[2] = {2}
• Index 3: value = 4 → mapper[4] = {1, 3} (4 appears again, so we add index 3)

After processing nums2, our mapper looks like:

mapper = {
    3: {0},
    4: {1, 3},
    2: {2}
}

Step 2: Create the mapping array

Now we process each element in nums1:

• nums1[0] = 4:

  • Look up mapper[4] = {1, 3}
  • Pop one index (let's say we get 1)
  • mapping[0] = 1
  • mapper[4] now contains {3}

• nums1[1] = 2:

  • Look up mapper[2] = {2}
  • Pop the index 2
  • mapping[1] = 2
  • mapper[2] now empty

• nums1[2] = 4:

  • Look up mapper[4] = {3}
  • Pop the index 3
  • mapping[2] = 3
  • mapper[4] now empty

• nums1[3] = 3:

  • Look up mapper[3] = {0}
  • Pop the index 0
  • mapping[3] = 0
  • mapper[3] now empty

Final Result: mapping = [1, 2, 3, 0]

We can verify this is correct:

• nums1[0] = 4 maps to nums2[1] = 4 ✓
• nums1[1] = 2 maps to nums2[2] = 2 ✓
• nums1[2] = 4 maps to nums2[3] = 4 ✓
• nums1[3] = 3 maps to nums2[0] = 3 ✓

Notice how the algorithm naturally handled the duplicate value (4) by storing both of its indices and using them one at a time.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input arrays.

• Building the mapper dictionary takes O(n) time as we iterate through nums2 once
• Creating the result list with list comprehension takes O(n) time as we iterate through nums1 once
• The pop() operation on a set is O(1) on average
• Total: O(n) + O(n) = O(n)

Space Complexity: O(n) where n is the length of the input arrays.

• The mapper dictionary stores at most n key-value pairs (in the worst case when all elements in nums2 are unique)
• Each value in the dictionary is a set that collectively stores n indices across all sets
• The output list requires O(n) space
• Total auxiliary space (excluding output): O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using a List Instead of a Set for Index Storage

The Problem: A common mistake is using a list to store indices instead of a set:

# Incorrect approach
index_map = defaultdict(list)
for index, number in enumerate(nums2):
    index_map[number].append(index)

# Then trying to remove used indices
result = []
for number in nums1:
    result.append(index_map[number].pop(0))  # O(n) operation!

Why it's problematic:

• pop(0) on a list is an O(n) operation because all remaining elements need to shift
• This degrades the overall time complexity from O(n) to O(n²) in the worst case
• For large arrays with many duplicates, this becomes significantly slower

The Solution: Use a set (as in the original code) or pop from the end of the list:

# Option 1: Use set with pop() - O(1) average
index_map = defaultdict(set)
result = [index_map[number].pop() for number in nums1]

# Option 2: Use list but pop from the end - O(1)
index_map = defaultdict(list)
result = [index_map[number].pop() for number in nums1]  # pop() without argument

Pitfall 2: Not Handling the Mutation of the Index Map

The Problem: If you need to use the solution multiple times or preserve the original mapping for later use:

def anagramMappings(self, nums1, nums2):
    index_map = defaultdict(set)
    for index, number in enumerate(nums2):
        index_map[number].add(index)
  
    # First call works fine
    result1 = [index_map[number].pop() for number in nums1]
  
    # Second call fails - sets are now empty!
    result2 = [index_map[number].pop() for number in nums1]  # KeyError!

The Solution: If you need to preserve the mapping, create a copy or use a non-destructive approach:

# Option 1: Create a copy for consumption
import copy
index_map_copy = copy.deepcopy(index_map)
result = [index_map_copy[number].pop() for number in nums1]

# Option 2: Use iterator-based approach (non-destructive)
from collections import defaultdict, deque

index_map = defaultdict(deque)
for index, number in enumerate(nums2):
    index_map[number].append(index)

# Convert to iterators
iterators = {num: iter(indices) for num, indices in index_map.items()}
result = [next(iterators[number]) for number in nums1]

Pitfall 3: Assuming Order Preservation in Set.pop()

The Problem: Some might expect set.pop() to return elements in a specific order:

# Incorrect assumption
# Expecting pop() to return indices in ascending order
s = {0, 1, 2, 3}
first = s.pop()  # Might not be 0!

Why it matters:

• Sets are unordered in Python (though implementation details have changed in Python 3.7+)
• pop() returns an arbitrary element, not necessarily the "first" or "smallest"
• If a specific mapping order is required (e.g., smallest available index), the current solution won't work

The Solution: If you need a specific order, use a different data structure:

# For smallest index first
index_map = defaultdict(list)
for index, number in enumerate(nums2):
    index_map[number].append(index)

# Sort each list once (or use heapq for better performance)
for indices in index_map.values():
    indices.sort(reverse=True)  # Reverse so we can pop from end

result = [index_map[number].pop() for number in nums1]