# Shortest Word Distance

Easy

Given a list of words and two words*word1\_and\_word2*, return the shortest distance between these two words in the list.

**Example:**\
Assume that words =`["practice", "makes", "perfect", "coding", "makes"]`.

```
Input: word1 = “coding”, word2 = “practice”
Output: 3
```

```
Input: word1 = "makes", word2 = "coding"
Output: 1
```

**Note:**\
You may assume that *word1* **does not equal to** *word2*, and \_word1 \_and \_word2 \_are both in the list.

## Solution

### One pass - O(n) time, O(1) space

We can greatly improve on the brute-force approach by keeping two indices i1 and i2 where we store the most recent locations of word1 and word2. Each time we find a new occurrence of one of the words, we do not need to search the entire array for the other word, since we already have the index of its most recent occurrence.

```java
class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int i1 = -1;
        int i2 = -1;
        int shortest = Integer.MAX_VALUE;

        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                i1 = i;
            }
            if (words[i].equals(word2)) {
                i2 = i;
            }

            if (i1 != -1 && i2 != -1) {
                shortest = Math.min(Math.abs(i1 - i2), shortest);
            }
        }
        return shortest;
    }
}
```

## Reference

<https://leetcode.com/problems/shortest-word-distance/solution/>