Find Anagram Mappings - Solution & Explanation

Problem Overview: You are given two integer arrays nums1 and nums2 where nums2 is an anagram of nums1. The task is to return an array mapping such that mapping[i] is the index j where nums1[i] == nums2[j]. Since the arrays are anagrams, every value in nums1 appears somewhere in nums2.

Approach 1: Brute Force Search (O(n²) time, O(1) space)

The most direct method is to scan nums2 for every element in nums1. For each index i in nums1, iterate through nums2 until you find a matching value and store that index in the result array. This works because the problem guarantees both arrays contain the same multiset of values. The drawback is the nested iteration: each lookup in nums2 may take up to O(n), resulting in overall O(n²) time. Space usage stays O(1) aside from the output array. This approach is acceptable for small inputs but does not scale well.

Approach 2: Hash Table Mapping (O(n) time, O(n) space)

A faster solution uses a hash map to record where each value appears in nums2. First iterate through nums2 and store value → index in a hash table. Then iterate through nums1 and perform constant‑time lookups to retrieve the corresponding index from the map. Each lookup takes O(1) on average, so the entire algorithm runs in O(n) time with O(n) additional space for the map.

Handling duplicates requires a small adjustment. Instead of storing a single index, store a list (or stack) of indices for each value in nums2. When you encounter that value in nums1, pop one index from the list and place it into the result. This guarantees every occurrence is mapped correctly while preserving O(n) complexity.

This solution relies on a hash table for constant‑time lookups, a common pattern in many hash table problems. The iteration over the arrays is straightforward and uses basic array traversal. The key insight is that searching repeatedly is unnecessary when you can precompute the positions once.

Recommended for interviews: The hash table approach is the expected solution. Interviewers want to see that you recognize the repeated lookup pattern and replace it with constant‑time hashing. Mentioning the brute force solution first demonstrates understanding of the problem, while transitioning to the O(n) hash map optimization shows strong problem‑solving instincts.