LeetCode 245 - Shortest Word Distance III

Difficulty: 🟡 Medium
Topics: Array, String

Solution

Problem Understanding

The problem gives us an array of strings, wordsDict, and two target words, word1 and word2. We must find the minimum distance between any occurrence of these two words in the array.

The distance between two words is defined as the absolute difference between their indices in the array. For example, if "coding" appears at index 3 and "makes" appears at index 4, the distance is 1.

The important detail in this problem is that word1 and word2 may be the same word. This changes the logic significantly compared to the simpler version of the problem. If the two target words are different, we only need to track the latest position of each word. However, when both targets are identical, we must find the minimum distance between consecutive occurrences of that same word.

The input constraints tell us that:

The array can contain up to 10^5 words.
Each word length is small, at most 10.
Both target words are guaranteed to exist in the array.

Since the input size can be very large, any algorithm worse than linear time becomes risky. A quadratic solution could potentially perform up to 10^10 operations, which is far too slow.

There are several important edge cases to consider:

word1 and word2 are different words.
word1 and word2 are the same word.
The shortest distance occurs between consecutive occurrences.
The target words appear many times throughout the array.
The array length is minimal.
The optimal pair appears near the beginning or end of the array.

The guarantee that the words exist in the array simplifies implementation because we do not need to handle missing targets.

Approaches

Brute Force Approach

The brute force solution checks every possible pair of indices in the array.

We iterate through all positions i and j. Whenever wordsDict[i] matches one target and wordsDict[j] matches the other target, we compute the absolute difference abs(i - j) and update the minimum distance.

If the words are identical, we must ensure that we compare two different positions.

This method is correct because it explicitly examines every valid pair of occurrences and therefore cannot miss the optimal answer.

However, the time complexity is extremely inefficient. With n words, we potentially compare every pair of positions, resulting in O(n^2) time complexity. Given that n can be as large as 100000, this approach is too slow.

Optimal Approach

The key insight is that we do not need to compare every pair of occurrences.

As we scan the array from left to right, the only occurrence that matters for minimizing distance is the most recent relevant occurrence.

If word1 and word2 are different:

Track the latest index where word1 appeared.
Track the latest index where word2 appeared.
Whenever both have been seen, compute the current distance.

If word1 and word2 are the same:

We only need the distance between consecutive appearances.
Each time we encounter the word again, compute the difference between the current index and the previous occurrence.

This allows us to solve the problem in a single pass through the array.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Compares every valid pair of positions
Optimal	O(n)	O(1)	Single pass while tracking recent indices

Algorithm Walkthrough

Optimal Algorithm

Initialize a variable minimum_distance with a very large value.
Determine whether word1 and word2 are the same word. This affects how we track indices.
If the words are different:

Maintain two variables:
last_word1_index
last_word2_index
Initialize both to -1 to indicate they have not been seen yet.

Traverse the array from left to right using index i.
For each word:

If the current word equals word1, update last_word1_index.
If the current word equals word2, update last_word2_index.

After updating indices:

If both indices are valid, compute the distance:
abs(last_word1_index - last_word2_index)
Update minimum_distance if this distance is smaller.

If the words are the same:

Maintain a single variable previous_index.
Whenever the target word appears:
If previous_index already exists, compute:
i - previous_index
Update the minimum distance.
Set previous_index = i.

After processing the entire array, return minimum_distance.

Why it works

The algorithm works because the closest valid pair for any position must involve the most recent occurrence of the other target word.

When the words are different, any older occurrence would produce a larger distance than the newest one. Therefore, keeping only the latest index is sufficient.

When the words are the same, the shortest distance must occur between consecutive appearances. Any non-consecutive pair would necessarily have a larger distance because another occurrence lies between them.

Python Solution

from typing import List

class Solution:
    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        minimum_distance = float("inf")

        # Case where both target words are the same
        if word1 == word2:
            previous_index = -1

            for index, word in enumerate(wordsDict):
                if word == word1:
                    if previous_index != -1:
                        minimum_distance = min(
                            minimum_distance,
                            index - previous_index
                        )

                    previous_index = index

        # Case where target words are different
        else:
            last_word1_index = -1
            last_word2_index = -1

            for index, word in enumerate(wordsDict):
                if word == word1:
                    last_word1_index = index

                if word == word2:
                    last_word2_index = index

                if last_word1_index != -1 and last_word2_index != -1:
                    minimum_distance = min(
                        minimum_distance,
                        abs(last_word1_index - last_word2_index)
                    )

        return minimum_distance

The implementation begins by initializing the minimum distance to infinity so that any valid distance will replace it.

The code then separates the logic into two cases. This separation is important because identical target words require fundamentally different handling.

In the identical-word case, we track only the previous occurrence of the word. Every new occurrence forms a candidate pair with the immediately preceding occurrence. Since consecutive occurrences always produce the smallest possible distance for that segment, this guarantees correctness.

In the different-word case, we track the most recent index for each target word independently. After every update, if both words have been seen, we compute the current distance and update the answer if needed.

The algorithm performs exactly one pass through the array and uses only a few integer variables.

Go Solution

import "math"

func shortestWordDistance(wordsDict []string, word1 string, word2 string) int {
	minimumDistance := math.MaxInt32

	// Case where both target words are the same
	if word1 == word2 {
		previousIndex := -1

		for index, word := range wordsDict {
			if word == word1 {
				if previousIndex != -1 {
					distance := index - previousIndex

					if distance < minimumDistance {
						minimumDistance = distance
					}
				}

				previousIndex = index
			}
		}
	} else {
		// Case where target words are different
		lastWord1Index := -1
		lastWord2Index := -1

		for index, word := range wordsDict {
			if word == word1 {
				lastWord1Index = index
			}

			if word == word2 {
				lastWord2Index = index
			}

			if lastWord1Index != -1 && lastWord2Index != -1 {
				distance := lastWord1Index - lastWord2Index

				if distance < 0 {
					distance = -distance
				}

				if distance < minimumDistance {
					minimumDistance = distance
				}
			}
		}
	}

	return minimumDistance
}

The Go implementation closely mirrors the Python solution.

One small difference is that Go does not provide a built-in integer infinity value, so we initialize the answer using math.MaxInt32.

Another difference is that Go does not have a built-in absolute value function for integers in the standard library. Therefore, the absolute difference is computed manually.

Slices in Go are used naturally for array traversal, and no additional memory allocation is required beyond a few integer variables.

Worked Examples

Example 1

wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
word1 = "makes"
word2 = "coding"

Since the words are different, we track the latest index of each word.

Index	Word	last_word1_index	last_word2_index	Distance	Minimum
0	practice	-1	-1	-	inf
1	makes	1	-1	-	inf
2	perfect	1	-1	-	inf
3	coding	1	3	2	2
4	makes	4	3	1	1

Final answer:

Example 2

wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
word1 = "makes"
word2 = "makes"

Since the words are identical, we track consecutive occurrences.

Index	Word	previous_index	Distance	Minimum
0	practice	-1	-	inf
1	makes	1	-	inf
2	perfect	1	-	inf
3	coding	1	-	inf
4	makes	4	3	3

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The array is scanned exactly once
Space	O(1)	Only a few index variables are stored

The algorithm is optimal because every word in the array must be examined at least once. No auxiliary data structures proportional to the input size are used, so the memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        minimum_distance = float("inf")

        if word1 == word2:
            previous_index = -1

            for index, word in enumerate(wordsDict):
                if word == word1:
                    if previous_index != -1:
                        minimum_distance = min(
                            minimum_distance,
                            index - previous_index
                        )

                    previous_index = index
        else:
            last_word1_index = -1
            last_word2_index = -1

            for index, word in enumerate(wordsDict):
                if word == word1:
                    last_word1_index = index

                if word == word2:
                    last_word2_index = index

                if last_word1_index != -1 and last_word2_index != -1:
                    minimum_distance = min(
                        minimum_distance,
                        abs(last_word1_index - last_word2_index)
                    )

        return minimum_distance

solution = Solution()

# Provided example, different words
assert solution.shortestWordDistance(
    ["practice", "makes", "perfect", "coding", "makes"],
    "makes",
    "coding"
) == 1

# Provided example, same words
assert solution.shortestWordDistance(
    ["practice", "makes", "perfect", "coding", "makes"],
    "makes",
    "makes"
) == 3

# Consecutive occurrences of same word
assert solution.shortestWordDistance(
    ["a", "a", "b"],
    "a",
    "a"
) == 1

# Different words appearing once each
assert solution.shortestWordDistance(
    ["a", "b"],
    "a",
    "b"
) == 1

# Multiple occurrences with shortest distance in middle
assert solution.shortestWordDistance(
    ["a", "x", "b", "a", "b"],
    "a",
    "b"
) == 1

# Same word appearing many times
assert solution.shortestWordDistance(
    ["x", "y", "x", "x", "x"],
    "x",
    "x"
) == 1

# Shortest distance near end of array
assert solution.shortestWordDistance(
    ["a", "c", "d", "b", "a", "b"],
    "a",
    "b"
) == 1

# Minimal valid input with repeated word
assert solution.shortestWordDistance(
    ["z", "z"],
    "z",
    "z"
) == 1

# Targets separated by large distance
assert solution.shortestWordDistance(
    ["a", "x", "x", "x", "x", "b"],
    "a",
    "b"
) == 5

Test	Why
Different target words	Validates standard behavior
Same target word	Validates special-case logic
Consecutive repeated words	Ensures minimum distance can be 1
Single occurrence of each word	Validates simplest distinct-word case
Multiple mixed occurrences	Ensures tracking updates correctly
Many repeated identical words	Verifies consecutive comparison logic
Shortest pair near array end	Ensures full traversal is correct
Minimal repeated input	Validates smallest valid repeated-word case
Large separation	Ensures distance calculations remain correct

Edge Cases

One important edge case occurs when word1 and word2 are identical. A naive implementation designed for distinct words often fails here because it may compare a word occurrence with itself, producing distance 0, which is invalid. The implementation avoids this by tracking consecutive occurrences separately and always comparing two different indices.

Another important edge case is when the shortest distance is 1. This happens when the target words appear adjacent to each other. Some incorrect implementations delay updates or skip comparisons, potentially missing adjacent pairs. Since the algorithm updates distances immediately after each occurrence, adjacent matches are handled naturally.

A third important edge case is when one word appears many times before the other appears for the first time. For example:

["a", "a", "a", "a", "b"]

A buggy solution might incorrectly use stale indices or fail to update properly. The implementation always stores the latest occurrence of each target word, ensuring that once both words have been seen, the current minimum distance is computed correctly.

Another subtle edge case occurs with consecutive identical occurrences such as:

["x", "x", "x"]

The correct answer is 1, because the closest pair is formed by adjacent occurrences. The implementation correctly computes distances between consecutive appearances and therefore always captures the smallest possible gap.