Find Anagram Mappings

Easy

Google

1 view

Topics:

ArraysStrings

You are given two integer arrays, A and B, where B is an anagram of A. This means B contains the same elements as A, but possibly in a different order. Your task is to find an index mapping P from A to B. A mapping P[i] = j means the element at index i in A appears at index j in B.

Example:

A = [12, 28, 46, 32, 50]
B = [50, 12, 32, 46, 28]

In this case, a valid index mapping P would be [1, 4, 3, 2, 0] because:

A[0] = 12 is found at B[1], so P[0] = 1
A[1] = 28 is found at B[4], so P[1] = 4
A[2] = 46 is found at B[3], so P[2] = 3
A[3] = 32 is found at B[2], so P[3] = 2
A[4] = 50 is found at B[0], so P[4] = 0

Constraints:

Arrays A and B may contain duplicate elements.
If multiple valid mappings exist, you can return any one of them.
The lengths of A and B are equal and greater than or equal to 1.

Can you write a function that takes two integer arrays A and B as input and returns the index mapping P?

Find Anagram Mappings

Easy

Google

1 view

Topics:

ArraysStrings

Example:

A = [12, 28, 46, 32, 50]
B = [50, 12, 32, 46, 28]

In this case, a valid index mapping P would be [1, 4, 3, 2, 0] because:

A[0] = 12 is found at B[1], so P[0] = 1
A[1] = 28 is found at B[4], so P[1] = 4
A[2] = 46 is found at B[3], so P[2] = 3
A[3] = 32 is found at B[2], so P[3] = 2
A[4] = 50 is found at B[0], so P[4] = 0

Constraints:

Arrays A and B may contain duplicate elements.
If multiple valid mappings exist, you can return any one of them.
The lengths of A and B are equal and greater than or equal to 1.

Can you write a function that takes two integer arrays A and B as input and returns the index mapping P?

Solution

Problem: Find Anagram Mappings

Given two lists A and B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order of the elements in A.

We want to find an index mapping P from A to B. A mapping P[i] = j means the ith element in A appears in B at index j.

These lists A and B may contain duplicates. If there are multiple answers, output any of them.

For example, given

A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28]

We should return

[1, 4, 3, 2, 0]

Since P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of A appears at B[4], and so on.

Naive Solution

The naive solution is to iterate through each element in A, and then iterate through B to find the index where the element in A appears in B. We store the index in the result array.

def anagramMappings_naive(A, B):
    P = []
    for i in range(len(A)):
        for j in range(len(B)):
            if A[i] == B[j]:
                P.append(j)
                break
    return P

Big O Runtime: O(n^2), where n is the length of the lists.

Big O Space Usage: O(n), for the result array.

Optimal Solution

The optimal solution is to use a hash map to store the indices of each element in B. This way, we can quickly find the index of each element in A in B.

def anagramMappings(A, B):
    index_map = {}
    for i, num in enumerate(B):
        if num not in index_map:
            index_map[num] = []
        index_map[num].append(i)

    P = []
    for num in A:
        P.append(index_map[num].pop(0))
    return P

Big O Runtime: O(n), where n is the length of the lists.

Big O Space Usage: O(n), for the hash map.

Edge Cases

If A or B is empty, return an empty array.
If A and B have different lengths, it is not an anagram, return an empty array.
If A and B have duplicate values, the solution must account for all duplicates. The optimal solution code above accounts for duplicates.

Solution

Problem: Find Anagram Mappings

Given two lists A and B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order of the elements in A.

We want to find an index mapping P from A to B. A mapping P[i] = j means the ith element in A appears in B at index j.

These lists A and B may contain duplicates. If there are multiple answers, output any of them.

For example, given

A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28]

We should return

[1, 4, 3, 2, 0]

Since P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of A appears at B[4], and so on.

Naive Solution

The naive solution is to iterate through each element in A, and then iterate through B to find the index where the element in A appears in B. We store the index in the result array.

def anagramMappings_naive(A, B):
    P = []
    for i in range(len(A)):
        for j in range(len(B)):
            if A[i] == B[j]:
                P.append(j)
                break
    return P

Big O Runtime: O(n^2), where n is the length of the lists.

Big O Space Usage: O(n), for the result array.

Optimal Solution

The optimal solution is to use a hash map to store the indices of each element in B. This way, we can quickly find the index of each element in A in B.

def anagramMappings(A, B):
    index_map = {}
    for i, num in enumerate(B):
        if num not in index_map:
            index_map[num] = []
        index_map[num].append(i)

    P = []
    for num in A:
        P.append(index_map[num].pop(0))
    return P

Big O Runtime: O(n), where n is the length of the lists.

Big O Space Usage: O(n), for the hash map.

Edge Cases

If A or B is empty, return an empty array.
If A and B have different lengths, it is not an anagram, return an empty array.
If A and B have duplicate values, the solution must account for all duplicates. The optimal solution code above accounts for duplicates.