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:

abs(i - j)

The problem guarantees that:

word1 != word2

and both words exist in wordsDict.

Input and Output

Example function shape:

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

Examples

Consider:

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:

abs(3 - 0) = 3

The answer is:

3

Another example:

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:

"coding" at index 3
"makes" at index 4

Their distance is:

abs(4 - 3) = 1

So the answer is:

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.

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:

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:

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:

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:

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

Implementation

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.

last1 = -1

We use last2 to remember the latest position of word2.

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.

answer = float("inf")

Then we scan every word with its index.

for i, word in enumerate(wordsDict):

If the current word is word1, we update last1.

if word == word1:
    last1 = i

If the current word is word2, we update last2.

elif word == word2:
    last2 = i

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

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

Finally, we return the shortest distance found.

return answer

Testing

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()