LeetCode 760: Find Anagram Mappings

Problem Restatement

We are given two integer arrays:

nums1
nums2

nums2 is an anagram of nums1.

That means nums2 contains exactly the same values as nums1, but possibly in a different order.

We need to return an array mapping where:

mapping[i] = j

means:

nums1[i] == nums2[j]

If there are multiple valid answers, we can return any of them.

Input and Output

Example function shape:

def anagramMappings(nums1: list[int], nums2: list[int]) -> list[int]:
    ...

Examples

Example 1:

nums1 = [12, 28, 46, 32, 50]
nums2 = [50, 12, 32, 46, 28]

Output:

[1, 4, 3, 2, 0]

Check each mapping:

So the mapping is valid.

Example 2:

nums1 = [84, 46]
nums2 = [84, 46]

Output:

[0, 1]

Each value already appears at the same index.

First Thought: Search in nums2

For every value in nums1, we can scan nums2 to find the same value.

for x in nums1:
    find x in nums2

This works, but it repeats the same search many times.

If both arrays have length n, this takes:

O(n^2)

We can do better by remembering where values appear in nums2.

Key Insight

We need fast lookup:

value -> index in nums2

So we build a hash map from each value in nums2 to its index.

Then for each value in nums1, we can directly look up the matching index.

Since the problem allows any valid answer, duplicates are simple. If a value appears multiple times, mapping all equal values to the same matching index is still accepted by the usual problem definition because each position only needs to satisfy:

nums1[i] == nums2[mapping[i]]

Algorithm

1. Create an empty dictionary index.
2. Scan nums2.
3. For every position j, store:

index[nums2[j]] = j

4. Create the answer by looking up each value from nums1:

mapping.append(index[nums1[i]])

5. Return mapping.

Correctness

Since nums2 is an anagram of nums1, every value in nums1 appears at least once in nums2.

The dictionary index stores an index where each value appears in nums2. Therefore, for every position i, looking up index[nums1[i]] returns some index j such that:

nums2[j] == nums1[i]

The algorithm sets:

mapping[i] = j

So every returned mapping position satisfies the required condition.

Because the problem allows any valid mapping when multiple answers exist, choosing any stored matching index is sufficient.

Therefore, the returned array is a valid anagram mapping.

Complexity

Let n = len(nums1) = len(nums2).

Implementation

class Solution:
    def anagramMappings(self, nums1: list[int], nums2: list[int]) -> list[int]:
        index = {}

        for j, value in enumerate(nums2):
            index[value] = j

        mapping = []

        for value in nums1:
            mapping.append(index[value])

        return mapping

Code Explanation

We first create a dictionary:

index = {}

Then we scan nums2:

for j, value in enumerate(nums2):
    index[value] = j

This records where each value appears.

For example:

nums2 = [50, 12, 32, 46, 28]

creates:

{
    50: 0,
    12: 1,
    32: 2,
    46: 3,
    28: 4,
}

Then we scan nums1:

for value in nums1:
    mapping.append(index[value])

Each value is looked up in the dictionary, and the matching index is appended to the answer.

Finally:

return mapping

returns the mapping array.

Handling Duplicates With Distinct Indices

The simple dictionary version is enough when any matching index is accepted.

If you want every duplicate occurrence to map to a different index, store a list of indices for each value.

from collections import defaultdict

class Solution:
    def anagramMappings(self, nums1: list[int], nums2: list[int]) -> list[int]:
        positions = defaultdict(list)

        for j, value in enumerate(nums2):
            positions[value].append(j)

        mapping = []

        for value in nums1:
            mapping.append(positions[value].pop())

        return mapping

For example:

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

The value 4 appears at indices 1 and 3 in nums2.

The list-based version can assign the first 4 to one index and the second 4 to the other.

Testing

def is_valid_mapping(nums1, nums2, mapping):
    if len(mapping) != len(nums1):
        return False

    for i, j in enumerate(mapping):
        if j < 0 or j >= len(nums2):
            return False

        if nums1[i] != nums2[j]:
            return False

    return True

def run_tests():
    s = Solution()

    nums1 = [12, 28, 46, 32, 50]
    nums2 = [50, 12, 32, 46, 28]
    assert is_valid_mapping(nums1, nums2, s.anagramMappings(nums1, nums2))

    nums1 = [84, 46]
    nums2 = [84, 46]
    assert is_valid_mapping(nums1, nums2, s.anagramMappings(nums1, nums2))

    nums1 = [1, 2]
    nums2 = [2, 1]
    assert is_valid_mapping(nums1, nums2, s.anagramMappings(nums1, nums2))

    nums1 = [4, 2, 4, 3]
    nums2 = [3, 4, 2, 4]
    assert is_valid_mapping(nums1, nums2, s.anagramMappings(nums1, nums2))

    print("all tests passed")

run_tests()

Test meaning: