760. Find Anagram Mappings - Explanation

Description

You are given two integer arrays nums1 and nums2 where nums2 is an anagram of nums1. Both arrays may contain duplicates.

Return an index mapping array mapping from nums1 to nums2 where mapping[i] = j means the i^th element in nums1 appears in nums2 at index j. If there are multiple answers, return any of them.

An array a is an anagram of an array b means b is made by randomizing the order of the elements in a.

Example 1:

Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]

Output: [1,4,3,2,0]

Explanation: As mapping[0] = 1 because the 0th element of nums1 appears at nums2[1], and mapping[1] = 4 because the 1st element of nums1 appears at nums2[4], and so on.

Example 2:

Input: nums1 = [84,46], nums2 = [84,46]

Output: [0,1]

Constraints:

1 <= nums1.length <= 100
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 10^5
nums2 is an anagram of nums1

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # List to store the anagram mappings.
        mappings = [0] * len(nums1)
        
        for i in range(len(nums1)):
            for j in range(len(nums2)):
                # Store the corresponding index of number in the second list.
                if nums1[i] == nums2[j]:
                    mappings[i] = j
                    break
        
        return mappings

Time & Space Complexity

Time complexity: $O(N^2)$
Space complexity: $O(1)$ constant space

Where $N$ is the number of integers in the list nums1 and nums2.

2. HashMap

class Solution:
    def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # Store the index corresponding to the value in the second list.
        valueToPos = {}
        for i in range(len(nums2)):
            valueToPos[nums2[i]] = i

        # List to store the anagram mappings.
        mappings = [0] * len(nums1)
        for i in range(len(nums1)):
            mappings[i] = valueToPos[nums1[i]]

        return mappings

Time & Space Complexity

Time complexity: $O(N)$
Space complexity: $O(N)$

Where $N$ is the number of integers in the list nums1 and nums2.

3. Bit Manipulation + Sorting

class Solution:
    def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]:
        bitsToShift = 7
        numToGetLastBits = (1 << bitsToShift) - 1
        
        # Store the index within the integer itself.
        for i in range(len(nums1)):
            nums1[i] = (nums1[i] << bitsToShift) + i
            nums2[i] = (nums2[i] << bitsToShift) + i
        
        # Sort both lists so that the original integers end up at the same index.
        nums1.sort()
        nums2.sort()
        
        # List to store the anagram mappings.
        mappings = [0] * len(nums1)
        
        for i in range(len(nums1)):
            # Store the index in the second list corresponding to the integer index in the first list.
            mappings[nums1[i] & numToGetLastBits] = (nums2[i] & numToGetLastBits)
        
        return mappings

Time & Space Complexity

Time complexity: $O(N \log N)$
Space complexity: $O(\log N)$

Where $N$ is the number of integers in the list nums1 and nums2.