Find Anagram Mappings

Find Anagram Mappings

What is this problem about?

The Find Anagram Mappings coding problem involves two arrays, A and B, where B is an anagram of A. This means B contains the same elements as A, but possibly in a different order. You need to return an index mapping array mapping where mapping[i] = j such that A[i] == B[j]. If there are multiple possible mappings (due to duplicate elements), any one will suffice.

Why is this asked in interviews?

This is a introductory question often used by Google to test knowledge of the Hash Table interview pattern. It evaluations whether you can use a lookup table to optimize what would otherwise be an $O(N^2)$ search into a linear $O(N)$ solution. It’s a basic test of data structure selection and attention to how duplicates are handled in a mapping context.

Algorithmic pattern used

This problem uses a Hash Map to store the indices of elements in the second array.

1. Iterate through array B.
2. Store each element and its index in a Map: {value: index}.
   • To handle duplicates, store a list of indices: {value: [index1, index2, ...]}.
3. Iterate through array A.
4. For each element A[i], look up its index in the Map and store it in the result array.

Example explanation

A = [12, 28, 46], B = [46, 12, 28]

1. Map from B: {46: 0, 12: 1, 28: 2}.
2. Map A[0] (12): Result[0] = 1.
3. Map A[1] (28): Result[1] = 2.
4. Map A[2] (46): Result[2] = 0. Result: [1, 2, 0].

Common mistakes candidates make

• Inefficient nested loops: Scanning B for every element in A, leading to $O(N^2)$ complexity.
• Handling duplicates incorrectly: If A = [10, 10] and B = [10, 10], failing to provide a valid mapping for both indices.
• Forgetting indices: Storing only the presence of an element in the map rather than its position.

Interview preparation tip

When you need to find "where did this item move to?", always think of a Hash Map. Mapping values to their positions is a fundamental building block for many complex algorithms, including string transformations and sorting optimizations.