Prerequisites
Before attempting this problem, you should be comfortable with:
- Hash Maps - Used to store value-to-index mappings for O(1) lookup
- Array Traversal - Basic iteration to build mappings between two arrays
- Bit Manipulation (Optional) - The advanced solution encodes indices into values using bit shifts
1. Brute Force
Intuition
The problem asks us to find, for each element in nums1, an index in nums2 where that same value appears. The simplest approach is to check every position in nums2 for each element in nums1. When we find a match, we record that index and move on. This guarantees correctness since we examine all possibilities.
Algorithm
- Create a result array
mappingsof the same length asnums1. - For each index
iinnums1:- Iterate through
nums2with indexj. - When
nums1[i]equalsnums2[j], storejinmappings[i]and break.
- Iterate through
- Return the
mappingsarray.
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 mappingsTime & Space Complexity
- Time complexity:
- Space complexity: constant space
Where is the number of integers in the list
nums1andnums2.
2. HashMap
Intuition
Instead of scanning nums2 repeatedly, we can preprocess it into a hash map that stores each value's index. This allows us to look up the corresponding index for any element in constant time. Since both arrays are anagrams, every element in nums1 is guaranteed to exist in nums2.
Algorithm
- Build a hash map
valueToPoswhere each key is a value fromnums2and each entry stores its index. - Create a result array
mappings. - For each element in
nums1, look up its index in the hash map and store it inmappings. - Return
mappings.
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 mappingsTime & Space Complexity
- Time complexity:
- Space complexity:
Where is the number of integers in the list
nums1andnums2.
3. Bit Manipulation + Sorting
Intuition
We can avoid using extra hash map space by encoding each element's original index directly into the element itself using bit manipulation. By left-shifting each value and adding its index, we preserve both pieces of information in a single integer. After sorting both arrays, elements with the same original value will align at the same positions, letting us extract and pair up their indices.
Algorithm
- For each index
i, encode both arrays:nums[i] = (nums[i] << 7) + i. The shift amount (7bits) must be large enough to hold the maximum index. - Sort both
nums1andnums2. Equal values now appear at matching positions. - Create the result array
mappings. - For each position
i, extract the original indices using a bitmask:mappings[nums1[i] & mask] = nums2[i] & mask. - Return
mappings.
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 mappingsTime & Space Complexity
- Time complexity:
- Space complexity:
Where is the number of integers in the list
nums1andnums2.
Common Pitfalls
Overwriting Indices for Duplicate Values
When using a hash map, storing only a single index per value means duplicate values all map to the same index. If the problem requires distinct mappings for duplicates, use a list of indices or pop from a stack of indices instead.
Off-by-One Errors in Bit Manipulation
When encoding indices into values using bit shifts, using too few bits causes index collisions for larger arrays. Ensure the shift amount is large enough to accommodate the maximum possible index value.