Find Anagram Mappings - Practice Coding Problems

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 array 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 a is an anagram of an array b means b is made by randomizing the order of the elements in a.

Input & Output

Example 1 — Basic Mapping

$ Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]

› Output: [1,4,3,2,0]

💡 Note: 12 maps to index 1, 28 maps to index 4, 46 maps to index 3, 32 maps to index 2, 50 maps to index 0

Example 2 — With Duplicates

$ Input: nums1 = [84,46], nums2 = [84,46]

› Output: [0,1]

💡 Note: nums1[0]=84 maps to nums2[0]=84, nums1[1]=46 maps to nums2[1]=46

Example 3 — Multiple Same Values

$ Input: nums1 = [40,40,40], nums2 = [40,40,40]

› Output: [0,1,2]

💡 Note: First 40 maps to index 0, second 40 maps to index 1, third 40 maps to index 2

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums1 = [12,28,46,32] and nums2 = [46,12,32,28] (anagram)

Find Mapping

For each nums1[i], find where that value appears in nums2

Output Indices

Return array [1,3,0,2] showing the index mappings

Key Takeaway

🎯 Key Insight: Build a value-to-indices mapping for instant lookups instead of searching linearly

Asked in

G Google 25 A Amazon 18 f Facebook 12

The key insight is to create a mapping from values to their indices in nums2. The optimal approach uses a hash map to store each value and its list of indices, then processes nums1 to build the result mapping in O(n) time.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map with Index Tracking	O(n)	O(n)	Build a hash map of value to list of indices in nums2, then lookup each nums1 element
Brute Force Linear Search	O(n²)	O(n)	For each element in nums1, search linearly through nums2 to find its first occurrence

Hash Map with Index Tracking — Algorithm Steps

Build hash map: value → list of indices in nums2
For each element in nums1, lookup its indices and pick the first unused one
Remove used index from the list

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Map

Create map: 46→[0], 12→[1], 32→[2], 28→[3]

Lookup

For nums1[0]=12, lookup map[12] and get first index [1]

Consume

Remove used index from map[12], continue for remaining elements

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VAL 1001
#define MAX_SIZE 1000

typedef struct {
    int indices[MAX_SIZE];
    int count;
    int used;
} IndexList;

int* solution(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    *returnSize = nums1Size;
    int* result = (int*)malloc(nums1Size * sizeof(int));
    
    // Simple hash map using array (assuming values are small)
    IndexList indexMap[MAX_VAL];
    memset(indexMap, 0, sizeof(indexMap));
    
    // Build index map
    for (int i = 0; i < nums2Size; i++) {
        int val = nums2[i] + 500; // offset for negative values
        indexMap[val].indices[indexMap[val].count++] = i;
    }
    
    // Build result
    for (int i = 0; i < nums1Size; i++) {
        int val = nums1[i] + 500;
        result[i] = indexMap[val].indices[indexMap[val].used++];
    }
    
    return result;
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int nums1[100], nums2[100];
    int n1 = 0, n2 = 0;
    
    char* p = strchr(line1, '[') + 1;
    while (*p != ']') {
        nums1[n1++] = atoi(p);
        while (*p != ',' && *p != ']') p++;
        if (*p == ',') p++;
    }
    
    p = strchr(line2, '[') + 1;
    while (*p != ']') {
        nums2[n2++] = atoi(p);
        while (*p != ',' && *p != ']') p++;
        if (*p == ',') p++;
    }
    
    int returnSize;
    int* result = solution(nums1, n1, nums2, n2, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

First pass through nums2 takes O(n), second pass through nums1 takes O(n), hash map operations are O(1) average

✓ Linear Growth

Space Complexity

O(n)

Hash map stores all indices, worst case is O(n) when all elements are different

⚡ Linearithmic Space

32.5K Views

Medium Frequency

~15 min Avg. Time

684 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map with Index Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler