# LeetCode 599: Minimum Index Sum of Two Lists

## Problem Restatement

We are given two string arrays, `list1` and `list2`.

A common string is a string that appears in both arrays.

For each common string, compute its index sum:

```text
index in list1 + index in list2
```

We need to return all common strings with the smallest index sum. The answer may be returned in any order.

The problem guarantees that both lists have unique strings and that there is at least one common string. The list lengths are between `1` and `1000`.

## Input and Output

| Item | Meaning |
|---|---|
| `list1` | First list of strings |
| `list2` | Second list of strings |
| Output | All common strings with the minimum index sum |
| Order | Any order is accepted |

Example function shape:

```python
def findRestaurant(list1: list[str], list2: list[str]) -> list[str]:
    ...
```

## Examples

Example 1:

```python
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
```

Output:

```python
["Shogun"]
```

The only common string is `"Shogun"`.

Example 2:

```python
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["KFC", "Shogun", "Burger King"]
```

Output:

```python
["Shogun"]
```

Common strings:

| String | Index in `list1` | Index in `list2` | Index Sum |
|---|---:|---:|---:|
| `"Shogun"` | 0 | 1 | 1 |
| `"Burger King"` | 2 | 2 | 4 |
| `"KFC"` | 3 | 0 | 3 |

The smallest index sum is `1`, so the answer is `["Shogun"]`.

Example 3:

```python
list1 = ["happy", "sad", "good"]
list2 = ["sad", "happy", "good"]
```

Output:

```python
["sad", "happy"]
```

Both `"happy"` and `"sad"` have index sum `1`, so both are returned.

## First Thought: Compare Every Pair

A direct solution is to compare every string in `list1` with every string in `list2`.

If the strings match, compute the index sum.

This works, but it takes:

```text
O(len(list1) * len(list2))
```

With lists up to length `1000`, this is still possible, but we can do better with a hash map.

## Key Insight

We need to quickly answer:

```text
Where does this string appear in list1?
```

A hash map can store:

```text
restaurant name -> index in list1
```

Then we scan `list2`.

For each string in `list2`, if it appears in the hash map, it is common to both lists. We compute:

```text
index_map[name] + index_in_list2
```

Then we track the smallest sum seen so far.

## Algorithm

1. Build a hash map from each string in `list1` to its index.
2. Initialize:
   - `best_sum = infinity`
   - `answer = []`
3. Scan `list2` with index `j`.
4. If `list2[j]` exists in the hash map:
   - Compute `current_sum = index_map[list2[j]] + j`.
   - If `current_sum < best_sum`, replace the answer with this string.
   - If `current_sum == best_sum`, append this string.
5. Return `answer`.

## Correctness

The hash map stores the exact index of every string in `list1`.

When the algorithm scans `list2`, every common string is detected because it appears in the hash map. For each detected common string, the algorithm computes its exact index sum.

The variable `best_sum` always stores the smallest index sum among the common strings processed so far. When a smaller sum is found, the previous answer list is cleared because those strings no longer have the minimum sum. When an equal sum is found, the string is appended because it is also optimal.

After the scan finishes, every common string has been considered exactly once. Therefore, `answer` contains exactly all common strings with the minimum index sum.

## Complexity

Let:

```text
m = len(list1)
n = len(list2)
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m + n)` | Build one hash map, then scan the second list |
| Space | `O(m)` | Store indices for strings in `list1` |

String hashing also depends on string length, but each string length is at most `30` in the constraints.

## Implementation

```python
class Solution:
    def findRestaurant(self, list1: list[str], list2: list[str]) -> list[str]:
        index = {}

        for i, name in enumerate(list1):
            index[name] = i

        best_sum = float("inf")
        answer = []

        for j, name in enumerate(list2):
            if name not in index:
                continue

            current_sum = index[name] + j

            if current_sum < best_sum:
                best_sum = current_sum
                answer = [name]
            elif current_sum == best_sum:
                answer.append(name)

        return answer
```

## Code Explanation

This builds the lookup table:

```python
index = {}

for i, name in enumerate(list1):
    index[name] = i
```

Since strings in `list1` are unique, each name maps to exactly one index.

The best sum starts as infinity:

```python
best_sum = float("inf")
```

The result list stores all strings tied for the best sum:

```python
answer = []
```

Then we scan `list2`:

```python
for j, name in enumerate(list2):
```

If the name is not in `list1`, it cannot be part of the answer:

```python
if name not in index:
    continue
```

For a common string, compute the index sum:

```python
current_sum = index[name] + j
```

If this sum is smaller than every previous sum, replace the answer:

```python
if current_sum < best_sum:
    best_sum = current_sum
    answer = [name]
```

If this sum ties the best known value, append it:

```python
elif current_sum == best_sum:
    answer.append(name)
```

Finally:

```python
return answer
```

returns all common strings with the smallest index sum.

## Testing

```python
def normalize(values):
    return sorted(values)

def run_tests():
    s = Solution()

    assert normalize(
        s.findRestaurant(
            ["Shogun", "Tapioca Express", "Burger King", "KFC"],
            ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"],
        )
    ) == normalize(["Shogun"])

    assert normalize(
        s.findRestaurant(
            ["Shogun", "Tapioca Express", "Burger King", "KFC"],
            ["KFC", "Shogun", "Burger King"],
        )
    ) == normalize(["Shogun"])

    assert normalize(
        s.findRestaurant(
            ["happy", "sad", "good"],
            ["sad", "happy", "good"],
        )
    ) == normalize(["sad", "happy"])

    assert normalize(
        s.findRestaurant(
            ["a", "b", "c"],
            ["c", "b", "a"],
        )
    ) == normalize(["b"])

    assert normalize(
        s.findRestaurant(
            ["a"],
            ["a"],
        )
    ) == normalize(["a"])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| One common string | Basic case |
| Multiple common strings | Chooses smallest index sum |
| Tie | Returns all tied strings |
| Middle item wins | Minimum may not be first common string found |
| Single-item lists | Minimum valid input |