Find Anagram Mappings

Problem

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 arraymapping fromnums1 tonums2 wheremapping[i] = j means theith element innums1 appears innums2 at indexj. 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.

Examples

Example 1:

1
2
3


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:

1
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.

Solution

Method 1 – Hash Map Indexing

Intuition

Since nums2 is an anagram of nums1, every element in nums1 appears in nums2. We can map each value in nums2 to its indices, then for each value in nums1, pick an unused index from nums2.

Approach

Build a hash map from value to a list of indices for nums2.
For each value in nums1, pop an index from the corresponding list in the map and add it to the answer.
Return the answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
public:
    vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, vector<int>> idx;
        for (int i = 0; i < nums2.size(); ++i) idx[nums2[i]].push_back(i);
        vector<int> ans;
        for (int x : nums1) {
            ans.push_back(idx[x].back());
            idx[x].pop_back();
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func anagramMappings(nums1, nums2 []int) []int {
    idx := map[int][]int{}
    for i, x := range nums2 { idx[x] = append(idx[x], i) }
    ans := make([]int, len(nums1))
    for i, x := range nums1 {
        n := len(idx[x])
        ans[i] = idx[x][n-1]
        idx[x] = idx[x][:n-1]
    }
    return ans
}

1
2
3
4
5
6
7
8
9


class Solution {
    public int[] anagramMappings(int[] nums1, int[] nums2) {
        Map<Integer, Deque<Integer>> idx = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) idx.computeIfAbsent(nums2[i], k -> new ArrayDeque<>()).add(i);
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) ans[i] = idx.get(nums1[i]).removeLast();
        return ans;
    }
}

1
2
3
4
5
6
7


class Solution {
    fun anagramMappings(nums1: IntArray, nums2: IntArray): IntArray {
        val idx = mutableMapOf<Int, ArrayDeque<Int>>()
        for ((i, x) in nums2.withIndex()) idx.getOrPut(x) { ArrayDeque() }.add(i)
        return nums1.map { idx[it]!!.removeLast() }.toIntArray()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def anagramMappings(self, nums1: list[int], nums2: list[int]) -> list[int]:
        from collections import defaultdict
        idx = defaultdict(list)
        for i, x in enumerate(nums2):
            idx[x].append(i)
        ans = []
        for x in nums1:
            ans.append(idx[x].pop())
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


use std::collections::HashMap;
impl Solution {
    pub fn anagram_mappings(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let mut idx = HashMap::new();
        for (i, &x) in nums2.iter().enumerate() {
            idx.entry(x).or_insert(vec![]).push(i as i32);
        }
        nums1.iter().map(|&x| idx.get_mut(&x).unwrap().pop().unwrap()).collect()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution {
    anagramMappings(nums1: number[], nums2: number[]): number[] {
        const idx = new Map<number, number[]>();
        nums2.forEach((x, i) => {
            if (!idx.has(x)) idx.set(x, []);
            idx.get(x)!.push(i);
        });
        return nums1.map(x => idx.get(x)!.pop()!);
    }
}

Complexity

⏰ Time complexity: O(n), where n is the length of nums1/nums2. We build the map and process each element once.
🧺 Space complexity: O(n), for the hash map storing indices.

Problem#

Examples#

Solution#

Method 1 – Hash Map Indexing#

Intuition#

Approach#

Code#

Complexity#