Problem Description

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

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|.

An important note is that word1 and word2 might be the same string. When they are the same, you need to find the minimum distance between two different occurrences of that word in the array. The problem guarantees that when word1 equals word2, there are at least two occurrences of that word in the array.

The solution handles two distinct cases:

• When word1 == word2: Track consecutive occurrences of the same word and calculate the minimum distance between them
• When word1 != word2: Track the most recent positions of both words and update the minimum distance whenever both have been found

The algorithm maintains a running minimum distance, initially set to the length of the array (maximum possible distance). As it iterates through the array, it updates this minimum whenever it finds valid pairs of the target words.

Intuition

The key insight is that we need to track positions of words as we scan through the array, but the strategy differs based on whether we're looking for the same word or different words.

When looking for the minimum distance between two different words, we can use a greedy approach. As we scan the array, we only need to remember the most recent position of each word. Why? Because if we find word1 at position i, the closest word2 to it would be the most recently seen word2 before position i or the next word2 we encounter after position i. There's no need to remember all previous positions.

The situation becomes slightly different when word1 and word2 are the same. In this case, we're looking for the minimum distance between two occurrences of the same word. We can't compare a word's position with itself, so we need to track consecutive occurrences. Each time we find the word, we calculate the distance from the previous occurrence and update our minimum if needed.

The initialization of indices to -1 serves as a flag to indicate whether we've encountered the words yet. For the different words case, we only start calculating distances after we've seen both words at least once (both indices are not -1). For the same word case, we start calculating distances after seeing the word at least twice.

By maintaining a running minimum and updating it whenever we find valid pairs, we ensure we've considered all possible distances by the time we finish scanning the array. The initial value of ans = len(wordsDict) acts as an upper bound since no distance in the array can exceed the array's length.

Solution Approach

The implementation uses case analysis to handle two distinct scenarios based on whether word1 and word2 are the same string.

Case 1: When word1 == word2

We need to find the minimum distance between two different occurrences of the same word. The algorithm:

• Initializes a variable j = -1 to track the previous occurrence index
• Iterates through wordsDict with index i
• When we find the target word:
  • If j != -1 (meaning we've seen the word before), calculate the distance i - j and update the minimum
  • Update j = i to remember this position for the next occurrence
• This ensures we're always comparing consecutive occurrences of the same word

Case 2: When word1 != word2

We need to find the minimum distance between any occurrence of word1 and any occurrence of word2. The algorithm:

• Initializes two variables i = j = -1 to track the most recent positions of word1 and word2
• Iterates through wordsDict with index k
• When we find word1, update i = k
• When we find word2, update j = k
• If both i != -1 and j != -1 (both words have been found at least once), calculate the distance abs(i - j) and update the minimum
• This greedy approach works because at any point, the closest pair involves the most recent occurrence of one word with the most recent occurrence of the other

The time complexity is O(n) where n is the length of wordsDict, as we make a single pass through the array. The space complexity is O(1) as we only use a constant amount of extra variables regardless of input size.

The initial value ans = len(wordsDict) serves as an upper bound that will definitely be replaced by a smaller valid distance during execution.

Example Walkthrough

Let me demonstrate the solution approach with two examples to cover both cases.

Example 1: Different words

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

Let's trace through the algorithm:

• Initialize: ans = 5 (array length), i = -1, j = -1
• Index 0: "the" → not a target word, continue
• Index 1: "quick" → matches word1, set i = 1
  • Both words not found yet (j = -1), no distance calculation
• Index 2: "brown" → not a target word, continue
• Index 3: "fox" → matches word2, set j = 3
  • Both words found (i = 1, j = 3)
  • Calculate distance: |1 - 3| = 2
  • Update ans = min(5, 2) = 2
• Index 4: "quick" → matches word1, set i = 4
  • Both words found (i = 4, j = 3)
  • Calculate distance: |4 - 3| = 1
  • Update ans = min(2, 1) = 1

Result: 1 (minimum distance between "quick" at index 4 and "fox" at index 3)

Example 2: Same word

wordsDict = ["a", "c", "a", "b", "a"]
word1 = "a", word2 = "a"

Since word1 == word2, we use the same-word logic:

• Initialize: ans = 5 (array length), j = -1
• Index 0: "a" → matches target word
  • j = -1 (first occurrence), no distance calculation
  • Update j = 0
• Index 1: "c" → not the target word, continue
• Index 2: "a" → matches target word
  • j = 0 (previous occurrence exists)
  • Calculate distance: 2 - 0 = 2
  • Update ans = min(5, 2) = 2
  • Update j = 2
• Index 3: "b" → not the target word, continue
• Index 4: "a" → matches target word
  • j = 2 (previous occurrence exists)
  • Calculate distance: 4 - 2 = 2
  • Update ans = min(2, 2) = 2
  • Update j = 4

Result: 2 (minimum distance between consecutive occurrences of "a")

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array wordsDict.

The algorithm iterates through the wordsDict array exactly once in both cases (whether word1 == word2 or word1 != word2). In each iteration, it performs constant-time operations such as comparisons, assignments, and calculating the minimum value. Therefore, the overall time complexity is linear with respect to the size of the input array.

Space Complexity: O(1).

The algorithm uses only a constant amount of extra space regardless of the input size. It maintains a few integer variables (ans, i, j, k) to track positions and the minimum distance. No additional data structures that grow with the input size are created, resulting in constant space complexity.

Common Pitfalls

Pitfall 1: Not Handling the Same Word Case Correctly

A critical mistake is treating the problem as if it always involves two different words. When word1 == word2, using the same tracking logic as for different words will result in a distance of 0, since you'd be comparing the same occurrence with itself.

Incorrect approach:

# This fails when word1 == word2
last_pos1 = -1
last_pos2 = -1
for i, word in enumerate(wordsDict):
    if word == word1:
        last_pos1 = i
    if word == word2:
        last_pos2 = i
    if last_pos1 != -1 and last_pos2 != -1:
        min_distance = min(min_distance, abs(last_pos1 - last_pos2))
# Returns 0 when word1 == word2 (wrong!)

Solution: Use separate logic branches. When the words are the same, track consecutive occurrences:

if word1 == word2:
    prev_index = -1
    for i, word in enumerate(wordsDict):
        if word == word1:
            if prev_index != -1:
                min_distance = min(min_distance, i - prev_index)
            prev_index = i

Pitfall 2: Using elif Instead of if for Word Matching

When word1 != word2, a word in the array might need to be checked against both target words. Using elif would skip the second check if the first matches, potentially missing valid updates.

Incorrect approach:

# This misses cases where a word could match both conditions
if word == word1:
    word1_index = current_index
elif word == word2:  # Wrong! Should be 'if'
    word2_index = current_index

Solution: Use two independent if statements to ensure both conditions are checked:

if word == word1:
    word1_index = current_index
if word == word2:  # Separate if statement
    word2_index = current_index

Pitfall 3: Incorrect Distance Calculation for Same Word

When finding the distance between two occurrences of the same word, forgetting to update the previous index after calculating the distance leads to incorrect comparisons in subsequent iterations.

Incorrect approach:

if word1 == word2:
    prev = -1
    for i, word in enumerate(wordsDict):
        if word == word1 and prev != -1:
            min_distance = min(min_distance, i - prev)
            # Forgot to update prev = i here!

Solution: Always update the previous index after finding a match, regardless of whether a distance was calculated:

if word == word1:
    if prev != -1:
        min_distance = min(min_distance, i - prev)
    prev = i  # Always update for the next comparison