# LeetCode 243: Shortest Word Distance

## Problem Restatement

We are given a list of words, `wordsDict`, and two different words, `word1` and `word2`.

Both words appear in the list.

We need to return the shortest distance between any occurrence of `word1` and any occurrence of `word2`.

The distance between two words is the absolute difference between their indices.

For example, if `word1` appears at index `i` and `word2` appears at index `j`, then the distance is:

```python
abs(i - j)
```

The problem guarantees that:

```python
word1 != word2
```

and both words exist in `wordsDict`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `wordsDict`, `word1`, and `word2` |
| Output | The minimum index distance between the two words |
| Constraint | `word1` and `word2` are different |
| Guarantee | Both words appear in the list |

Example function shape:

```python
def shortestDistance(wordsDict: list[str], word1: str, word2: str) -> int:
    ...
```

## Examples

Consider:

```python
wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
word1 = "coding"
word2 = "practice"
```

The word `"coding"` appears at index `3`.

The word `"practice"` appears at index `0`.

So the distance is:

```python
abs(3 - 0) = 3
```

The answer is:

```python
3
```

Another example:

```python
wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
word1 = "makes"
word2 = "coding"
```

The word `"makes"` appears at indices `1` and `4`.

The word `"coding"` appears at index `3`.

The closest pair is:

```python
"coding" at index 3
"makes" at index 4
```

Their distance is:

```python
abs(4 - 3) = 1
```

So the answer is:

```python
1
```

## First Thought: Brute Force

The simplest solution is to collect every index where `word1` appears and every index where `word2` appears.

Then compare every pair.

```python
class Solution:
    def shortestDistance(self, wordsDict: list[str], word1: str, word2: str) -> int:
        positions1 = []
        positions2 = []

        for i, word in enumerate(wordsDict):
            if word == word1:
                positions1.append(i)
            elif word == word2:
                positions2.append(i)

        answer = float("inf")

        for i in positions1:
            for j in positions2:
                answer = min(answer, abs(i - j))

        return answer
```

This works because it checks every possible pair of positions.

## Problem With Brute Force

If `word1` appears many times and `word2` also appears many times, comparing every pair can be too slow.

For example, if each word appears about `n / 2` times, then the number of comparisons can be close to:

```python
O(n^2)
```

We can do better because the list already has a natural left-to-right order.

## Key Insight

We only need to remember the latest seen index of each word.

As we scan from left to right:

```python
last1 = latest index of word1
last2 = latest index of word2
```

Whenever we see either target word, we update its latest index.

If both latest indices are known, we compute the distance between them.

Why is this enough?

At index `i`, the closest previous occurrence of the other word is its most recent occurrence. Any older occurrence is farther away because it has a smaller index.

So a single pass is enough.

## Algorithm

Initialize:

```python
last1 = -1
last2 = -1
answer = float("inf")
```

Then scan `wordsDict`.

For each index `i` and word `word`:

1. If `word == word1`, set `last1 = i`.
2. If `word == word2`, set `last2 = i`.
3. If both `last1` and `last2` are known, update:

```python
answer = min(answer, abs(last1 - last2))
```

Return `answer`.

## Correctness

At every step, `last1` stores the latest index of `word1` seen so far, and `last2` stores the latest index of `word2` seen so far.

When we encounter `word1`, the best possible match among all previously seen `word2` positions is the latest `word2` position, because it is closest to the current index. The same reasoning holds when we encounter `word2`.

Therefore, every time a closer valid pair can appear, the algorithm checks it immediately.

Since the algorithm scans all words from left to right, it considers the closest relevant previous occurrence for every occurrence of both target words. Thus, the minimum value stored in `answer` is the shortest distance between `word1` and `word2`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the list once |
| Space | `O(1)` | We only store two indices and the answer |

## Implementation

```python
class Solution:
    def shortestDistance(self, wordsDict: list[str], word1: str, word2: str) -> int:
        last1 = -1
        last2 = -1
        answer = float("inf")

        for i, word in enumerate(wordsDict):
            if word == word1:
                last1 = i
            elif word == word2:
                last2 = i

            if last1 != -1 and last2 != -1:
                answer = min(answer, abs(last1 - last2))

        return answer
```

## Code Explanation

We use `last1` to remember the latest position of `word1`.

```python
last1 = -1
```

We use `last2` to remember the latest position of `word2`.

```python
last2 = -1
```

The value `-1` means the word has not been seen yet.

The variable `answer` starts at infinity because we want to minimize it.

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

Then we scan every word with its index.

```python
for i, word in enumerate(wordsDict):
```

If the current word is `word1`, we update `last1`.

```python
if word == word1:
    last1 = i
```

If the current word is `word2`, we update `last2`.

```python
elif word == word2:
    last2 = i
```

After that, if both words have appeared at least once, we update the best distance.

```python
if last1 != -1 and last2 != -1:
    answer = min(answer, abs(last1 - last2))
```

Finally, we return the shortest distance found.

```python
return answer
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.shortestDistance(
        ["practice", "makes", "perfect", "coding", "makes"],
        "coding",
        "practice",
    ) == 3

    assert s.shortestDistance(
        ["practice", "makes", "perfect", "coding", "makes"],
        "makes",
        "coding",
    ) == 1

    assert s.shortestDistance(
        ["a", "b"],
        "a",
        "b",
    ) == 1

    assert s.shortestDistance(
        ["a", "c", "b", "a", "b"],
        "a",
        "b",
    ) == 1

    assert s.shortestDistance(
        ["x", "a", "x", "x", "b", "x", "a"],
        "a",
        "b",
    ) == 2

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example | Checks the basic problem statement |
| Repeated word | Confirms we choose the closest occurrence |
| Two elements | Checks the minimum valid input shape |
| Alternating close pair | Confirms later occurrences can improve the answer |
| Words far apart | Confirms distance calculation works across unrelated words |