Problem Description

You are given an array of strings wordsDict and two strings word1 and word2 that both exist in the array. Your task is to find the shortest distance between these two words in the array.

The distance between two words is calculated as the absolute difference between their indices in the array. For example, if word1 appears at index i and word2 appears at index j, the distance between them is |i - j|.

Since the same word can appear multiple times in the array, there might be multiple pairs of positions for word1 and word2. You need to find the minimum distance among all possible pairs.

Example:

• If wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", and word2 = "practice"
• "coding" is at index 3 and "practice" is at index 0
• The distance is |3 - 0| = 3

The solution uses a single pass through the array, keeping track of the most recent positions of both word1 and word2. Whenever either word is encountered, it updates the corresponding position and calculates the distance if both words have been seen at least once. The minimum distance is maintained throughout the traversal.

Intuition

The key insight is that we only need to track the most recent occurrence of each word as we traverse the array. Why? Because the minimum distance will always involve consecutive occurrences of the two different words.

Think about it this way: if we have positions of word1 at indices [2, 5, 8] and word2 at indices [1, 4, 7], the minimum distance won't be between word1 at index 2 and word2 at index 7. It will be between adjacent pairs like (2,1), (5,4), or (8,7).

This is because as we move through the array linearly, whenever we encounter one of our target words, the closest occurrence of the other word must be the one we saw most recently. Any earlier occurrence would be farther away.

For example, if we're at position 5 and find word1, and we last saw word2 at position 4, the distance is |5-4| = 1. Even if word2 also appeared at position 1, that distance |5-1| = 4 would be larger.

This observation allows us to solve the problem in a single pass with O(1) space. We maintain two variables i and j to store the most recent positions of word1 and word2 respectively. Each time we find either word, we update its position and calculate the distance if we've seen both words at least once (indicated by both i and j not being -1). We keep track of the minimum distance found so far, which becomes our answer.

Solution Approach

We implement a single-pass algorithm using two pointer variables to track the most recent positions of each word:

1. Initialize tracking variables: Set i = j = -1 to indicate that neither word has been found yet. Initialize ans = inf to store the minimum distance.

2. Traverse the array: Use enumerate() to iterate through wordsDict with both index k and word w.

3. Update positions:

   • When we encounter word1, update i = k to store its latest position
   • When we encounter word2, update j = k to store its latest position

4. Calculate distance: After each update, check if both words have been found (i != -1 and j != -1). If so, calculate the distance as abs(i - j) and update the minimum: ans = min(ans, abs(i - j)).

5. Return result: After traversing the entire array, return ans which holds the minimum distance found.

The algorithm works because at any point during traversal, variables i and j hold the most recent positions of word1 and word2 respectively. Since we're looking for the minimum distance, we only need to consider the closest pair, which will always involve the most recent occurrence of one word with the most recent occurrence of the other.

Time Complexity: O(n) where n is the length of wordsDict, as we make a single pass through the array.

Space Complexity: O(1) as we only use a constant amount of extra space for variables i, j, and ans.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input: wordsDict = ["the", "quick", "brown", "fox", "quick"], word1 = "the", word2 = "quick"

Step-by-step execution:

Initially: i = -1, j = -1, ans = infinity

Index 0: word = "the"

• Found word1! Update i = 0
• Check if both found: i = 0, j = -1 → No, skip distance calculation
• Current state: i = 0, j = -1, ans = infinity

Index 1: word = "quick"

• Found word2! Update j = 1
• Check if both found: i = 0, j = 1 → Yes! Calculate distance
• Distance = |0 - 1| = 1
• Update minimum: ans = min(infinity, 1) = 1
• Current state: i = 0, j = 1, ans = 1

Index 2: word = "brown"

• Not either target word, continue
• Current state: i = 0, j = 1, ans = 1

Index 3: word = "fox"

• Not either target word, continue
• Current state: i = 0, j = 1, ans = 1

Index 4: word = "quick"

• Found word2! Update j = 4
• Check if both found: i = 0, j = 4 → Yes! Calculate distance
• Distance = |0 - 4| = 4
• Update minimum: ans = min(1, 4) = 1
• Current state: i = 0, j = 4, ans = 1

Final Result: The minimum distance is 1

The key insight demonstrated here is that we only keep the most recent position of each word. When "quick" appears again at index 4, we update j from 1 to 4. This doesn't improve our answer (distance becomes 4 instead of 1), but if "the" appeared later in the array, we'd want to compare with the most recent "quick" at index 4, not the older one at index 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of wordsDict. The algorithm iterates through the list exactly once, performing constant-time operations (comparisons, assignments, and min calculation) at each step.

Space Complexity: O(1). The algorithm uses only a fixed amount of extra space for variables i, j, ans, and k, regardless of the input size. No additional data structures are created that scale with the input.

Common Pitfalls

Pitfall 1: Handling the Case When word1 and word2 Are the Same

A critical edge case that's often overlooked is when word1 and word2 are identical strings. The current implementation will always return 0 in this case because both word1_index and word2_index will be updated to the same value whenever the word is found, resulting in abs(word1_index - word2_index) = 0.

However, the problem asks for the distance between two different occurrences of words. When the words are the same, we need to find the minimum distance between different instances of that word.

Incorrect behavior example:

• wordsDict = ["a", "b", "a"], word1 = "a", word2 = "a"
• Current code returns 0 (incorrect)
• Expected output: 2 (distance between indices 0 and 2)

Solution to the Pitfall

We need to handle two separate cases: when the words are different and when they're the same.

class Solution:
    def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        if word1 == word2:
            # Special case: find minimum distance between same word occurrences
            prev_index = -1
            min_distance = float('inf')
          
            for current_index, current_word in enumerate(wordsDict):
                if current_word == word1:
                    if prev_index != -1:
                        min_distance = min(min_distance, current_index - prev_index)
                    prev_index = current_index
          
            return min_distance
        else:
            # Original logic for different words
            word1_index = -1
            word2_index = -1
            min_distance = float('inf')
          
            for current_index, current_word in enumerate(wordsDict):
                if current_word == word1:
                    word1_index = current_index
                elif current_word == word2:
                    word2_index = current_index
              
                if word1_index != -1 and word2_index != -1:
                    min_distance = min(min_distance, abs(word1_index - word2_index))
          
            return min_distance

Alternative Unified Solution

A more elegant approach that handles both cases without branching:

class Solution:
    def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        prev_index = -1
        min_distance = float('inf')
      
        for current_index, current_word in enumerate(wordsDict):
            if current_word == word1 or current_word == word2:
                # If prev_index exists and either:
                # 1. Words are different, OR
                # 2. Words are same but we found another occurrence
                if prev_index != -1 and (word1 != word2 or wordsDict[prev_index] == current_word):
                    min_distance = min(min_distance, current_index - prev_index)
                prev_index = current_index
      
        return min_distance

This unified solution tracks only the previous relevant index and updates the minimum distance whenever appropriate, handling both same and different word cases seamlessly.