We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Anagram Mappings

Number: 762

Difficulty: Easy

Paid? Yes

Companies: Google

Problem Description

Given two integer arrays nums1 and nums2 where nums2 is an anagram of nums1, return an index mapping array mapping such that mapping[i] = j indicates the i-th element in nums1 appears at index j in nums2. If there are multiple valid mappings (due to duplicate elements), any valid mapping is acceptable.

Key Insights

  • Since nums2 is an anagram of nums1, every element in nums1 has a corresponding position in nums2.
  • A dictionary (or hash table) can be used to map each number in nums2 to its indices.
  • When iterating through nums1, we can assign the next available index from the dictionary for that number.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the arrays (single pass to build the dictionary and another pass to form the mapping). Space Complexity: O(n) for storing the dictionary that holds indices of elements in nums2.

Solution

The approach consists of two primary steps:

  1. Build a dictionary to record all indices where each number appears in nums2. This dictionary maps a number to a list of indices.
  2. Iterate over nums1 and for each element, remove (or pop) one index from the corresponding list in the dictionary, and add that index to the final mapping array. This guarantees that each number from nums1 is correctly mapped to one of its positions in nums2 while efficiently handling duplicates.

Code Solutions

# Build a dictionary mapping each number in nums2 to a list of its indices.
def anagramMappings(nums1, nums2):
    # Dictionary to store number : list of indices
    index_dict = {}
    for index, num in enumerate(nums2):
        if num in index_dict:
            index_dict[num].append(index)
        else:
            index_dict[num] = [index]
    
    mapping = []
    # Generate the mapping for each element in nums1.
    for num in nums1:
        # Pop the first available index for num and add it to mapping.
        mapping.append(index_dict[num].pop(0))
    return mapping

# Example usage:
nums1 = [12,28,46,32,50]
nums2 = [50,12,32,46,28]
print(anagramMappings(nums1, nums2))  # Output: [1,4,3,2,0] or any valid mapping
← Back to All Questions