Skip to content

760. Find Anagram Mappings πŸ”’

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 ith 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] <= 105
  • nums2 is an anagram of nums1.

Solutions

Solution 1: Hash Table

We use a hash table \(\textit{d}\) to store each element of the array \(\textit{nums2}\) and its corresponding index. Then we iterate through the array \(\textit{nums1}\), and for each element \(\textit{nums1}[i]\), we retrieve its corresponding index from the hash table \(\textit{d}\) and store it in the result array.

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the array.

1
2
3
4
class Solution:
    def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]:
        d = {x: i for i, x in enumerate(nums2)}
        return [d[x] for x in nums1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int[] anagramMappings(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Map<Integer, Integer> d = new HashMap<>(n);
        for (int i = 0; i < n; ++i) {
            d.put(nums2[i], i);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = d.get(nums1[i]);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        unordered_map<int, int> d;
        for (int i = 0; i < n; ++i) {
            d[nums2[i]] = i;
        }
        vector<int> ans;
        for (int x : nums1) {
            ans.push_back(d[x]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func anagramMappings(nums1 []int, nums2 []int) []int {
    d := map[int]int{}
    for i, x := range nums2 {
        d[x] = i
    }
    ans := make([]int, len(nums1))
    for i, x := range nums1 {
        ans[i] = d[x]
    }
    return ans
}

1
2
3
4
5
6
7
function anagramMappings(nums1: number[], nums2: number[]): number[] {
    const d: Map<number, number> = new Map();
    for (let i = 0; i < nums2.length; ++i) {
        d.set(nums2[i], i);
    }
    return nums1.map(num => d.get(num)!);
}

Comments