LeetCode 760 - Find Anagram Mappings

LeetCode Problem 760

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

The problem asks us to build an index mapping from nums1 to nums2, where nums2 is guaranteed to be an anagram of nums1. Since an anagram means the same elements appear in both arrays, but possibly in a different order, every value in nums1 must appear somewhere in nums2.

For each element nums1[i], we need to find an index j in nums2 such that:

nums1[i] == nums2[j]

The output is an integer array called mapping, where:

mapping[i] = j

This means the element at position i in nums1 appears at position j in nums2.

An important detail is that duplicates are allowed. This means a value can appear multiple times in both arrays. Because the problem explicitly states that any valid answer is acceptable, we do not need to find a unique or specific mapping for duplicate values. We only need to return a valid index correspondence.

For example:

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

The number 12 appears at index 1 in nums2, so the first element of the result is 1. Similarly, 28 appears at index 4, 46 appears at index 3, and so on.

The constraints are small:

• 1 <= nums1.length <= 100
• Values range from 0 to 10^5
• nums2 is guaranteed to be an anagram of nums1

Since the array length is at most 100, even a quadratic solution would pass comfortably. However, the problem is naturally suited for a hash table solution, which gives us linear time complexity.

The main edge case comes from duplicate numbers. A naive hash map that stores only one index per value may accidentally reuse the same index multiple times if duplicates exist. Since the problem accepts any valid answer, storing one valid index per number is sufficient in many cases, but a more robust implementation can store multiple indices if needed. Fortunately, because any valid answer is accepted and the input guarantee ensures matching frequencies, a simple hash map from value to one index works correctly.

Approaches

Brute Force Approach

The simplest approach is to iterate through each element in nums1 and search for it in nums2.

For every nums1[i], we scan all elements of nums2 until we find a matching value. Once found, we record its index.

This approach works because nums2 is guaranteed to contain every value from nums1. Therefore, every search will eventually succeed.

However, this method repeatedly scans the second array, which leads to unnecessary repeated work. For each element in nums1, we may examine up to all n elements of nums2.

Since there are n elements in nums1, the total complexity becomes quadratic.

Optimal Approach, Hash Map

The key observation is that repeated searching is wasteful. Since we will frequently ask:

"At what index does this value appear in nums2?"

we can preprocess nums2 into a hash map.

We create a dictionary where:

value -> index in nums2

Then, instead of scanning nums2 repeatedly, we can retrieve the index instantly using hash table lookup.

After building the hash map, we iterate through nums1 and append the corresponding mapped index for each value.

This reduces lookup time from O(n) to O(1) on average.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Scan nums2 for every element in nums1
Optimal	O(n)	O(n)	Use a hash map for constant time index lookup

Algorithm Walkthrough

Optimal Algorithm

1. Create an empty hash map called index_map.

This map will store the position of each value in nums2. The reason for using a hash map is that it provides average O(1) lookup time, which is much faster than repeatedly scanning the array. 2. Traverse nums2 and populate the hash map.

For each index i and value num in nums2, store:

index_map[num] = i

After this step, we can immediately find the index of any number in nums2. 3. Create an empty result array called mapping.

This array will hold the final answer. 4. Traverse nums1.

For each number num in nums1, look up its corresponding index in index_map and append it to mapping. 5. Return the mapping array.

Why it works

The correctness comes from the guarantee that nums2 is an anagram of nums1. This means every value in nums1 exists in nums2.

The hash map stores a valid index for every number in nums2. Therefore, every lookup during the second traversal succeeds. Since each mapped index corresponds to the same value, the resulting mapping satisfies the problem definition.

Even with duplicates, any valid mapping is accepted, and storing one valid occurrence is enough to produce a correct answer.

Python Solution

from typing import List

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

        for index, num in enumerate(nums2):
            index_map[num] = index

        mapping = []

        for num in nums1:
            mapping.append(index_map[num])

        return mapping

The implementation begins by constructing a dictionary called index_map. We iterate through nums2 using enumerate, which gives both the index and value at each position. Each number is stored as a key, while its index becomes the value.

After preprocessing nums2, we create the mapping list. We then iterate through nums1 and perform constant time lookups in index_map.

Because the dictionary already contains the index of every number, we simply append the mapped index to the result list.

Finally, we return the completed mapping array.

Go Solution

func anagramMappings(nums1 []int, nums2 []int) []int {
	indexMap := make(map[int]int)

	for index, num := range nums2 {
		indexMap[num] = index
	}

	mapping := make([]int, 0, len(nums1))

	for _, num := range nums1 {
		mapping = append(mapping, indexMap[num])
	}

	return mapping
}

The Go implementation follows the same logic as the Python version. A map[int]int is used to store the relationship between values and indices.

Instead of Python lists, Go uses slices. We initialize the mapping slice with capacity equal to len(nums1) to avoid unnecessary reallocations while appending.

There are no concerns about integer overflow because all values and indices are well within Go's int range. Since the problem guarantees valid input, we do not need to check whether a key exists before lookup.

Worked Examples

Example 1

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

Step 1: Build the hash map

Index	Value	Hash Map State
0	50	{50: 0}
1	12	{50: 0, 12: 1}
2	32	{50: 0, 12: 1, 32: 2}
3	46	{50: 0, 12: 1, 32: 2, 46: 3}
4	28	{50: 0, 12: 1, 32: 2, 46: 3, 28: 4}

Step 2: Build the mapping

Current Number	Lookup Result	Mapping State
12	1	[1]
28	4	[1,4]
46	3	[1,4,3]
32	2	[1,4,3,2]
50	0	[1,4,3,2,0]

Final result:

[1,4,3,2,0]

Example 2

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

Step 1: Build the hash map

Index	Value	Hash Map State
0	84	{84: 0}
1	46	{84: 0, 46: 1}

Step 2: Build the mapping

Current Number	Lookup Result	Mapping State
84	0	[0]
46	1	[0,1]

Final result:

[0,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to build the hash map and one pass to construct the result
Space	O(n)	The hash map stores up to n elements

The algorithm performs two linear traversals. The first traversal builds the hash map from nums2, and the second traversal constructs the answer using constant time hash lookups. Since hash map access is O(1) on average, the total runtime is linear.

The extra memory comes from storing indices in the hash map, which requires space proportional to the number of elements.

Test Cases

sol = Solution()

# Example 1
assert sol.anagramMappings(
    [12, 28, 46, 32, 50],
    [50, 12, 32, 46, 28]
) == [1, 4, 3, 2, 0]  # standard shuffled mapping

# Example 2
assert sol.anagramMappings(
    [84, 46],
    [84, 46]
) == [0, 1]  # identical arrays

# Single element array
assert sol.anagramMappings(
    [5],
    [5]
) == [0]  # minimum size input

# All identical values
result = sol.anagramMappings(
    [7, 7, 7],
    [7, 7, 7]
)
assert len(result) == 3  # duplicate values

# Reverse order
assert sol.anagramMappings(
    [1, 2, 3, 4],
    [4, 3, 2, 1]
) == [3, 2, 1, 0]  # reversed positions

# Contains zero
assert sol.anagramMappings(
    [0, 100000],
    [100000, 0]
) == [1, 0]  # boundary values

# Larger input
assert sol.anagramMappings(
    [1, 3, 5, 7, 9],
    [9, 7, 5, 3, 1]
) == [4, 3, 2, 1, 0]  # multiple lookups

Test	Why
[12,28,46,32,50]	Validates standard shuffled mapping
[84,46]	Verifies identical arrays
[5]	Tests minimum input size
[7,7,7]	Checks duplicate handling
Reversed order arrays	Ensures mapping works regardless of order
[0,100000]	Validates lower and upper value boundaries
Larger shuffled array	Stresses repeated hash lookups

Edge Cases

One important edge case is duplicate values. For example:

nums1 = [7,7,7]
nums2 = [7,7,7]

A naive implementation might worry about assigning unique indices to each duplicate. However, the problem explicitly allows any valid answer, meaning reusing the same valid index is acceptable. Since our hash map stores one occurrence of the number, the implementation still returns a correct mapping.

Another edge case is the minimum input size, where both arrays contain exactly one element. For example:

nums1 = [5]
nums2 = [5]

This case can expose off by one indexing mistakes or initialization bugs. Our implementation handles it naturally because the hash map contains one entry, and the single lookup succeeds.

A third edge case is arrays with values at the constraint boundaries, such as 0 and 100000. Large numeric ranges sometimes encourage inefficient solutions such as allocating huge arrays indexed by value. Our implementation avoids this issue by using a hash map, which stores only the values that actually appear.

Finally, an important guarantee is that nums2 is always an anagram of nums1. Because of this guarantee, we never need to handle missing elements or invalid lookups. Every number in nums1 is guaranteed to exist in nums2, making hash table access safe.