# LeetCode 760: Find Anagram Mappings

## Problem Restatement

We are given two integer arrays:

```python
nums1
nums2
```

`nums2` is an anagram of `nums1`.

That means `nums2` contains exactly the same values as `nums1`, but possibly in a different order.

We need to return an array `mapping` where:

```python
mapping[i] = j
```

means:

```python
nums1[i] == nums2[j]
```

If there are multiple valid answers, we can return any of them.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integer arrays `nums1` and `nums2` |
| Condition | `nums2` is an anagram of `nums1` |
| Output | An index mapping from `nums1` to `nums2` |
| Duplicate values | Any valid matching index is allowed |

Example function shape:

```python
def anagramMappings(nums1: list[int], nums2: list[int]) -> list[int]:
    ...
```

## Examples

Example 1:

```python
nums1 = [12, 28, 46, 32, 50]
nums2 = [50, 12, 32, 46, 28]
```

Output:

```python
[1, 4, 3, 2, 0]
```

Check each mapping:

| `i` | `nums1[i]` | `mapping[i]` | `nums2[mapping[i]]` |
|---:|---:|---:|---:|
| `0` | `12` | `1` | `12` |
| `1` | `28` | `4` | `28` |
| `2` | `46` | `3` | `46` |
| `3` | `32` | `2` | `32` |
| `4` | `50` | `0` | `50` |

So the mapping is valid.

Example 2:

```python
nums1 = [84, 46]
nums2 = [84, 46]
```

Output:

```python
[0, 1]
```

Each value already appears at the same index.

## First Thought: Search in `nums2`

For every value in `nums1`, we can scan `nums2` to find the same value.

```python
for x in nums1:
    find x in nums2
```

This works, but it repeats the same search many times.

If both arrays have length `n`, this takes:

```text
O(n^2)
```

We can do better by remembering where values appear in `nums2`.

## Key Insight

We need fast lookup:

```text
value -> index in nums2
```

So we build a hash map from each value in `nums2` to its index.

Then for each value in `nums1`, we can directly look up the matching index.

Since the problem allows any valid answer, duplicates are simple. If a value appears multiple times, mapping all equal values to the same matching index is still accepted by the usual problem definition because each position only needs to satisfy:

```python
nums1[i] == nums2[mapping[i]]
```

## Algorithm

1. Create an empty dictionary `index`.
2. Scan `nums2`.
3. For every position `j`, store:

```python
index[nums2[j]] = j
```

4. Create the answer by looking up each value from `nums1`:

```python
mapping.append(index[nums1[i]])
```

5. Return `mapping`.

## Correctness

Since `nums2` is an anagram of `nums1`, every value in `nums1` appears at least once in `nums2`.

The dictionary `index` stores an index where each value appears in `nums2`. Therefore, for every position `i`, looking up `index[nums1[i]]` returns some index `j` such that:

```python
nums2[j] == nums1[i]
```

The algorithm sets:

```python
mapping[i] = j
```

So every returned mapping position satisfies the required condition.

Because the problem allows any valid mapping when multiple answers exist, choosing any stored matching index is sufficient.

Therefore, the returned array is a valid anagram mapping.

## Complexity

Let `n = len(nums1) = len(nums2)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan `nums2` once and `nums1` once |
| Space | `O(n)` | The dictionary stores values from `nums2` |

## Implementation

```python
class Solution:
    def anagramMappings(self, nums1: list[int], nums2: list[int]) -> list[int]:
        index = {}

        for j, value in enumerate(nums2):
            index[value] = j

        mapping = []

        for value in nums1:
            mapping.append(index[value])

        return mapping
```

## Code Explanation

We first create a dictionary:

```python
index = {}
```

Then we scan `nums2`:

```python
for j, value in enumerate(nums2):
    index[value] = j
```

This records where each value appears.

For example:

```python
nums2 = [50, 12, 32, 46, 28]
```

creates:

```python
{
    50: 0,
    12: 1,
    32: 2,
    46: 3,
    28: 4,
}
```

Then we scan `nums1`:

```python
for value in nums1:
    mapping.append(index[value])
```

Each value is looked up in the dictionary, and the matching index is appended to the answer.

Finally:

```python
return mapping
```

returns the mapping array.

## Handling Duplicates With Distinct Indices

The simple dictionary version is enough when any matching index is accepted.

If you want every duplicate occurrence to map to a different index, store a list of indices for each value.

```python
from collections import defaultdict

class Solution:
    def anagramMappings(self, nums1: list[int], nums2: list[int]) -> list[int]:
        positions = defaultdict(list)

        for j, value in enumerate(nums2):
            positions[value].append(j)

        mapping = []

        for value in nums1:
            mapping.append(positions[value].pop())

        return mapping
```

For example:

```python
nums1 = [4, 2, 4, 3]
nums2 = [3, 4, 2, 4]
```

The value `4` appears at indices `1` and `3` in `nums2`.

The list-based version can assign the first `4` to one index and the second `4` to the other.

## Testing

```python
def is_valid_mapping(nums1, nums2, mapping):
    if len(mapping) != len(nums1):
        return False

    for i, j in enumerate(mapping):
        if j < 0 or j >= len(nums2):
            return False

        if nums1[i] != nums2[j]:
            return False

    return True

def run_tests():
    s = Solution()

    nums1 = [12, 28, 46, 32, 50]
    nums2 = [50, 12, 32, 46, 28]
    assert is_valid_mapping(nums1, nums2, s.anagramMappings(nums1, nums2))

    nums1 = [84, 46]
    nums2 = [84, 46]
    assert is_valid_mapping(nums1, nums2, s.anagramMappings(nums1, nums2))

    nums1 = [1, 2]
    nums2 = [2, 1]
    assert is_valid_mapping(nums1, nums2, s.anagramMappings(nums1, nums2))

    nums1 = [4, 2, 4, 3]
    nums2 = [3, 4, 2, 4]
    assert is_valid_mapping(nums1, nums2, s.anagramMappings(nums1, nums2))

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Main example | Confirms basic mapping |
| Same order | Values can map to same positions |
| Reversed order | Confirms lookup by value, not position |
| Duplicate values | Confirms any valid duplicate mapping works |