Problem Description

Given two integer arrays A and B of the same length, where B is an anagram of A, find an index mapping from A to B. That is, for each element in A, find an index in B such that A[i] == B[ans[i]]. The result should be an array ans of the same length as A, where ans[i] is the index in B such that B[ans[i]] == A[i].

• It is guaranteed that B is an anagram of A (i.e., both arrays contain the same elements, possibly in a different order).
• Each element in B can only be used once for mapping.
• There is always at least one valid answer.

Example:
A = [12, 28, 46, 32, 50]
B = [50, 12, 32, 46, 28]
Output: [1, 4, 3, 2, 0]

Thought Process

To solve this problem, the most direct approach is, for each element in A, to search through B for a matching value and record its index. However, this brute-force approach would be slow, especially for large arrays, since it would check every element in B for every element in A.

Instead, we can optimize by recognizing that B is an anagram of A, so every value in A must exist somewhere in B. If we could instantly know where every value in B is located, we could map each value from A to the correct index in B efficiently.

This leads to the idea of using a hash map (dictionary) to store the indices of each value in B. For values that appear more than once, we need to make sure we do not reuse the same index, so we can store a list of indices for each value.

Solution Approach

Here is a step-by-step breakdown of the efficient solution:

1. Build a mapping from value to indices in B:
   • Iterate through B and, for each value, store all its indices in a hash map (dictionary).
   • If a value appears multiple times, store all its indices in a list.
2. Map each element in A to an index in B:
   • For each value in A, look up the list of indices in the hash map.
   • Pop (remove) an index from the list and add it to the answer array.
   • This ensures each index in B is used only once, even for duplicates.
3. Return the answer array.

Why use a hash map? Because lookups and removals from a list are fast (O(1)), this approach is much more efficient than searching through B for every value.

Example Walkthrough

Let's walk through the example:

Input:
A = [12, 28, 46, 32, 50]
B = [50, 12, 32, 46, 28]

1. Build the mapping from B:
   50: [0]
12: [1]
32: [2]
46: [3]
28: [4]
2. Map each value in A:
   • 12: mapping[12] = [1] → pop 1 → ans = [1]
   • 28: mapping[28] = [4] → pop 4 → ans = [1, 4]
   • 46: mapping[46] = [3] → pop 3 → ans = [1, 4, 3]
   • 32: mapping[32] = [2] → pop 2 → ans = [1, 4, 3, 2]
   • 50: mapping[50] = [0] → pop 0 → ans = [1, 4, 3, 2, 0]
3. Final answer: [1, 4, 3, 2, 0]

Each value in A is mapped to a unique index in B that matches its value.

Time and Space Complexity

Brute-force approach:

• For each element in A (length n), search through B (n elements): O(n^2) time.
• Space: O(1) extra space (besides output).

• Building the mapping: O(n) time and O(n) space.
• Mapping A to B: O(n) time (since each lookup and pop is O(1)).
• Total: O(n) time and O(n) space.

The optimized approach is much faster and suitable for large arrays.

Code Implementation

from collections import defaultdict

class Solution:
    def anagramMappings(self, A, B):
        mapping = defaultdict(list)
        for idx, val in enumerate(B):
            mapping[val].append(idx)
        result = []
        for val in A:
            result.append(mapping[val].pop())
        return result
      

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> anagramMappings(vector<int>& A, vector<int>& B) {
        unordered_map<int, vector<int>> mapping;
        for (int i = 0; i < B.size(); ++i) {
            mapping[B[i]].push_back(i);
        }
        vector<int> result;
        for (int a : A) {
            result.push_back(mapping[a].back());
            mapping[a].pop_back();
        }
        return result;
    }
};
      

import java.util.*;

class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
        Map<Integer, Deque<Integer>> mapping = new HashMap<>();
        for (int i = 0; i < B.length; i++) {
            mapping.computeIfAbsent(B[i], k -> new ArrayDeque<>()).add(i);
        }
        int[] result = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            result[i] = mapping.get(A[i]).removeLast();
        }
        return result;
    }
}
      

var anagramMappings = function(A, B) {
    const mapping = {};
    for (let i = 0; i < B.length; i++) {
        if (!mapping[B[i]]) mapping[B[i]] = [];
        mapping[B[i]].push(i);
    }
    const result = [];
    for (const val of A) {
        result.push(mapping[val].pop());
    }
    return result;
};
      

Summary

The key to solving the "Find Anagram Mappings" problem efficiently is to use a hash map to record the indices of each value in B. By mapping each value in A to an available index in B and ensuring each index is used only once (by popping from the list), we avoid the inefficiency of brute-force searching. This approach is both simple and fast, making use of hash maps and lists to achieve O(n) time complexity. The solution is elegant because it leverages the properties of anagrams and efficient data structures for a clean, readable implementation.