Find Anagram Mappings

Easy

Asked by:

15 views

Topics:

ArraysStrings

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 mapping from nums1 to nums2 where mapping[i] = j means the i^th element in nums1 appears in nums2 at index j. If there are multiple answers, return any of them.

An array arr is an anagram of an array brr means that brr is made by rearranging the elements of arr.

Example 1:

Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
Output: [1,4,3,2,0]
Explanation: As nums1[0] = 12 appears in nums2[1] = 12, mapping[0] = 1.
nums1[1] = 28 appears in nums2[4] = 28, mapping[1] = 4.
nnums1[2] = 46 appears in nums2[3] = 46, mapping[2] = 3.
nnums1[3] = 32 appears in nums2[2] = 32, mapping[3] = 2.
nnums1[4] = 50 appears in nums2[0] = 50, mapping[4] = 0.

Example 2:

Input: nums1 = [84,46], nums2 = [84,46]
Output: [0,1]

Example 3:

Input: nums1 = [1,2], nums2 = [2,1]
Output: [1,0]

Constraints:

1 <= nums1.length <= 100
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 10⁵
nums2 is an anagram of nums1.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values within the input arrays A and B?
Are the input arrays A and B guaranteed to have the same length, and can I assume they are non-empty?
If multiple valid mappings exist, is any valid mapping acceptable, or is there a specific order or criteria I should use to determine which one to return?
Could there be duplicate values within either array A or array B, and if so, how should those be handled in determining the mapping?
If a number in A does not exist in B, is that invalid input, or how should the algorithm handle that case?

Brute Force Solution

Approach

The brute force approach for finding anagram mappings involves checking every single possible match between elements of the two input lists. It's like trying every possible pairing to see if it works. We will create a mapping for each element of the first list by searching for matching elements in the second list.

Here's how the algorithm would work step-by-step:

For each element in the first list, look at every single element in the second list.
If you find a match between the element from the first list and an element from the second list, record that match.
Continue checking the remaining elements in the second list for the current element in the first list, even if you already found a match (in case duplicates are allowed).
Repeat this process for every element in the first list.
The recorded matches will then form your mapping indicating which element in the second list corresponds to each element in the first list based on their values.

Code Implementation

def find_anagram_mappings_brute_force(first_list, second_list):
    anagram_mappings = []

    for first_list_index in range(len(first_list)):

        # Iterate through the second list for each element of the first
        for second_list_index in range(len(second_list)):
            if first_list[first_list_index] == second_list[second_list_index]:

                # Append the index if the values match
                anagram_mappings.append(second_list_index)
                break

    return anagram_mappings

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the 'n' elements in the first list. For each of these 'n' elements, it iterates through the second list, also of size 'n', to find a match. This nested iteration results in checking approximately n * n pairs. Therefore, the overall time complexity is O(n²).

Space Complexity

O(1) – The provided algorithm iterates through two lists, but the plain English explanation does not describe the use of any auxiliary data structures like lists, hash maps, or sets to store intermediate results or mappings. It only describes comparing elements directly. Therefore, the only memory used is for a few index variables, the number of which remains constant regardless of the size of the input lists. The space complexity is thus constant, O(1).

Optimal Solution

Approach

To efficiently find where the anagrams are, we create a quick lookup tool. This tool allows us to instantly find the location of each number from the second list within the first list, instead of searching every time.

Here's how the algorithm would work step-by-step:

Create a way to quickly find the location of numbers from the second list in the first list. Think of this as making a little address book.
Go through the first list, noting the position of each unique number.
Now, when you look at the second list, you can use your address book to directly jump to the location of each number in the first list.
Build a new list using the locations you found. This list will give you the mapping between the two lists.

Code Implementation

def find_anagram_mappings(list_a, list_b):
    # Create a dictionary to store indices of elements in list_a
    index_map_a = {}

    for index, number in enumerate(list_a):
        if number not in index_map_a:
            index_map_a[number] = []
        index_map_a[number].append(index)

    mapping = []
    # Iterate through list_b to find corresponding indices in list_a
    for number in list_b:
        # We use pop because we assume the input is a valid mapping, 
        # so we want to use each index in list_a only once.
        mapping.append(index_map_a[number].pop(0))

    return mapping

Big(O) Analysis

Time Complexity

O(n) – The algorithm's time complexity is driven by two main steps. First, creating the lookup tool (the address book) iterates through the first list A once, where n is the length of A. This operation takes O(n) time. Second, iterating through the second list B (which is also of length n) and using the lookup tool to find the index of each element takes O(n) time since each lookup is constant time due to the hash map/dictionary. Therefore, the overall time complexity is O(n) + O(n) which simplifies to O(n).

Space Complexity

O(N) – The algorithm creates an address book, which is essentially a hash map, to store the index (position) of each unique number from the first list. In the worst-case scenario, where all numbers in the first list are unique, the hash map will store N entries, where N is the size of the first list. Furthermore, a new list (the result) is built to store the mapping, and this list also has a size of N. Therefore, the auxiliary space used is proportional to N, making the space complexity O(N).

Edge Cases

Case	How to Handle
A or B is null or empty	Return an empty array or throw an exception if null or empty input is invalid based on the problem statement.
A and B have different lengths	Return an empty array or throw an exception, as anagram mappings are impossible if lengths differ.
A and B are identical arrays	The mapping should be [0, 1, 2, ..., n-1] where n is the array length.
A and B contain duplicate elements but the frequencies differ	This indicates that B is not an anagram of A, return an empty array or throw an exception.
A and B contain large numbers (potential integer overflow during hashing)	Use a data structure or hashing algorithm that can handle large numbers without overflow, such as long integers or strings as keys.
All elements in A are the same, and all elements in B are the same but in a different order	The mapping should assign each index in A to a valid index in B that holds the same repeated element.
Large input size exceeding available memory	Consider using a streaming approach or external sorting if the entire input cannot fit in memory.
Input arrays contain negative numbers	The solution should correctly handle negative numbers, for example, by using a hashmap that supports negative keys.

A or B is null or empty

How to Handle:

Return an empty array or throw an exception if null or empty input is invalid based on the problem statement.

A and B have different lengths

How to Handle:

Return an empty array or throw an exception, as anagram mappings are impossible if lengths differ.

A and B are identical arrays

How to Handle:

The mapping should be [0, 1, 2, ..., n-1] where n is the array length.

A and B contain duplicate elements but the frequencies differ

How to Handle:

This indicates that B is not an anagram of A, return an empty array or throw an exception.

A and B contain large numbers (potential integer overflow during hashing)

How to Handle:

Use a data structure or hashing algorithm that can handle large numbers without overflow, such as long integers or strings as keys.

All elements in A are the same, and all elements in B are the same but in a different order

How to Handle:

The mapping should assign each index in A to a valid index in B that holds the same repeated element.

Large input size exceeding available memory

How to Handle:

Consider using a streaming approach or external sorting if the entire input cannot fit in memory.

Input arrays contain negative numbers

How to Handle:

The solution should correctly handle negative numbers, for example, by using a hashmap that supports negative keys.