LeetCode 243: Shortest Word Distance - All Solutions Explained

Problem Statement

The Shortest Word Distance problem (LeetCode 243) requires finding the minimum distance between two given words in a list of words. The distance is measured by the absolute difference in their indices in the list.

Copy codeInput: words = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
Output: 3
Explanation: "coding" appears at index 3, "practice" at index 0 → distance = 3

Input: words = ["a", "b", "c", "d", "a", "b"], word1 = "a", word2 = "b"
Output: 1
Explanation: The closest pair is "a" at index 0 and "b" at index 1 → distance = 1

Solution 1: One Pass with Indices Tracking (Best Solution)

Explanation of the Best Solution

This approach maintains the most recent positions of both words as we iterate through the list:

1. Initialize variables:
2. index1 = -1 (last seen position of word1)
3. index2 = -1 (last seen position of word2)

4. min_distance = ∞ (minimum distance found)

5. Iterate through words:

6. Update index1 when word1 is found
7. Update index2 when word2 is found

8. If both indices are valid (≥ 0), calculate distance and update min_distance

9. Return result: The smallest distance found

Step-by-Step Example

For words = ["a", "b", "c", "d", "a", "b"], word1 = "a", word2 = "b": 1. i=0: "a" → index1=0, index2=-1 → no update 2. i=1: "b" → index1=0, index2=1 → distance=1 (new min) 3. i=2: "c" → no update 4. i=3: "d" → no update 5. i=4: "a" → index1=4, index2=1 → distance=3 (not better) 6. i=5: "b" → index1=4, index2=5 → distance=1 (matches min) Final result: 1

Python Code (One Pass)

Copy codedef shortestDistance(words: List[str], word1: str, word2: str) -> int:
    index1, index2 = -1, -1
    min_distance = float('inf')

    for i, word in enumerate(words):
        if word == word1:
            index1 = i
        elif word == word2:
            index2 = i

        if index1 != -1 and index2 != -1:
            min_distance = min(min_distance, abs(index1 - index2))

    return min_distance

Complexity

• Time Complexity: O(n) - single pass through the list
• Space Complexity: O(1) - constant extra space

Why It's the Best

• Most efficient solution
• Single pass through data
• Minimal memory usage
• Easy to understand and implement

Solution 2: Brute Force (For Understanding)

Explanation

This naive approach compares all occurrences of both words:

1. Find all indices of word1 and word2
2. Compare every pair of indices
3. Track the minimum absolute difference

Python Code (Brute Force)

Copy codedef shortestDistance(words: List[str], word1: str, word2: str) -> int:
    indices1 = [i for i, word in enumerate(words) if word == word1]
    indices2 = [i for i, word in enumerate(words) if word == word2]

    min_distance = float('inf')
    for i in indices1:
        for j in indices2:
            min_distance = min(min_distance, abs(i - j))

    return min_distance

Complexity

• Time Complexity: O(n + m×k) - where m and k are counts of word1 and word2
• Space Complexity: O(m + k) - storing indices lists

Pros and Cons

• Pros: Simple to understand
• Cons: Inefficient for frequent words

Solution 3: Hash Map Preprocessing (For Multiple Queries)

Explanation

This alternative preprocesses the data for multiple queries:

1. Preprocessing:
2. Create a dictionary mapping each word to its indices
3. Query processing:
4. Get sorted indices for both words
5. Use two pointers to find minimum difference

Python Code (Hash Map)

Copy codefrom collections import defaultdict

class WordDistance:
    def __init__(self, words: List[str]):
        self.word_indices = defaultdict(list)
        for i, word in enumerate(words):
            self.word_indices[word].append(i)

    def shortest(self, word1: str, word2: str) -> int:
        indices1 = self.word_indices[word1]
        indices2 = self.word_indices[word2]
        i, j = 0, 0
        min_distance = float('inf')

        while i < len(indices1) and j < len(indices2):
            min_distance = min(min_distance, abs(indices1[i] - indices2[j]))
            if indices1[i] < indices2[j]:
                i += 1
            else:
                j += 1

        return min_distance

Complexity

• Preprocessing: O(n) - one-time cost
• Query: O(m + k) - where m and k are occurrence counts
• Space: O(n) - storing all indices

When to Use

• When multiple queries will be made
• When preprocessing time can be amortized

Edge Cases to Consider

• Words appear consecutively
• One word appears multiple times, the other once
• Large input size (3×10⁴ words)
• Words at beginning and end of list
• Identical words (though constraints say word1 ≠ word2)

Final Thoughts

• One Pass Solution: Best for single queries
• Brute Force: Good for understanding the problem
• Hash Map: Optimal for multiple queries

For coding interviews, the one pass solution is strongly recommended as it demonstrates efficient single-pass algorithm design.