Find Anagram Mappings

Easy · Arrays & Hashing · Explanation and code example

Bit Manipulation + Sorting

How it works

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.

Steps

  1. For each index i, encode both arrays: nums[i] = (nums[i] << 7) + i. The shift amount (7 bits) must be large enough to hold the maximum index.
  2. Sort both nums1 and nums2. Equal values now appear at matching positions.
  3. Create the result array mappings.
  4. For each position i, extract the original indices using a bitmask: mappings[nums1[i] & mask] = nums2[i] & mask.
  5. Return mappings.

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.

Things to watch for

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.

Python code example

from typing import List

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

C++ code example

class Solution {
public:
    const int bitsToShift = 7;
    const int numToGetLastBits = (1 << bitsToShift) - 1;
    
    vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) {
        // Store the index within the integer itself.
        for (int i = 0; i < nums1.size(); i++) {
            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.
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        
        // List to store the anagram mappings.
        vector<int> mappings(nums1.size());
        for (int i = 0; i < nums1.size(); i++) {
            // 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;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations