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
AandBof equal length, containing integers.
Outputs:
- A list
PwhereP[i]is the index inBwhere the element at indexiinAappears.
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
- Create an empty dictionary
index_map. - Iterate through list
Band populateindex_mapwhere the key is the element fromBand the value is its index. - Initialize an empty list
P. - Iterate through list
A, for each element, use the dictionary to find its corresponding index inBand append this index toP. - Return the list
P.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the lists
AandB. 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 fromB.
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.