Domain 1EasyCORE

Find Anagram Mappings

We are given two lists `A` and `B`, where `B` is an anagram of `A`. This means that `B` contains the same elements as `A` but in a different order. The task is to find an index mapping `P` such that for each element in `A`, we know its corresponding index in `B`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table

760. Find Anagram Mappings

Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 81.9%


Problem Breakdown

We are given two lists A and B, where B is an anagram of A. This means that B contains the same elements as A but in a different order. The task is to find an index mapping P such that for each element in A, we know its corresponding index in B.

Inputs:

  • Two lists A and B of equal length, containing integers.

Outputs:

  • A list P where P[i] is the index in B where the element at index i in A appears.

Implicit Constraints or Tricky Edge Cases:

  • The lists may contain duplicates.
  • The lists are guaranteed to be of equal length and within a specified range.
  • The elements in the lists are integers within a specified range.

Intuition

The brute-force approach would involve, for each element in A, scanning through B to find its index. This approach has a time complexity of O(n^2) because for each element in A, we might have to scan all elements in B.

A better approach is to use a hash table (dictionary in Python) to store the indices of elements in B. This way, we can look up the index of any element in B in constant time, reducing the overall time complexity to O(n).

Approach

  1. Create an empty dictionary index_map.
  2. Iterate through list B and populate index_map where the key is the element from B and the value is its index.
  3. Initialize an empty list P.
  4. Iterate through list A, for each element, use the dictionary to find its corresponding index in B and append this index to P.
  5. Return the list P.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the lists A and B. We iterate through both lists once.
  • Space Complexity: O(n) for storing the dictionary index_map, which in the worst case could contain all elements from B.

Solution

def anagramMappings(A, B):
    index_map = {value: index for index, value in enumerate(B)}
    P = [index_map[value] for value in A]
    return P

Edge Cases Handled

  • Duplicates: The dictionary will store the last occurrence of each element in B. This is acceptable since any valid mapping can be returned.
  • Equal Lengths: The problem guarantees that both lists are of equal length, so no additional checks are needed for this condition.