LeetCode 243 - Shortest Word Distance
The problem gives us an array of strings called wordsDict, along with two distinct target words, word1 and word2. Both target words are guaranteed to exist somewhere in the array.
Difficulty: 🟢 Easy
Topics: Array, String
Solution
Problem Understanding
The problem gives us an array of strings called wordsDict, along with two distinct target words, word1 and word2. Both target words are guaranteed to exist somewhere in the array. Our goal is to compute the smallest distance between any occurrence of word1 and any occurrence of word2.
The distance between two words is defined as the absolute difference between their indices in the array. For example, if word1 appears at index 3 and word2 appears at index 7, then the distance is |7 - 3| = 4.
The input array represents a sequence of words in order. We must scan through this sequence and determine the closest pair of positions where the two target words appear.
The constraints provide important information about the expected solution efficiency:
- The array length can be as large as
3 * 10^4 - Each word is short, at most length
10 - Both target words are guaranteed to exist
word1 != word2
Because the array can contain tens of thousands of elements, inefficient quadratic solutions may become unnecessarily slow. This strongly suggests that we should aim for a linear time solution.
There are several edge cases worth identifying early:
- The two words may appear next to each other, producing a distance of
1 - One or both words may appear multiple times
- The closest pair may not involve the first occurrence of either word
- The words may appear at the beginning or end of the array
- The array may contain many unrelated words between occurrences
The guarantee that both words exist simplifies the implementation because we never need to handle missing targets.
Approaches
Brute Force Approach
A straightforward solution is to first collect all indices where word1 appears and all indices where word2 appears. After that, we compare every index from the first list against every index from the second list and compute the absolute distance.
For example:
word1positions:[1, 5, 10]word2positions:[3, 8]
We would compute:
|1 - 3||1 - 8||5 - 3||5 - 8||10 - 3||10 - 8|
Then we return the minimum value.
This approach is correct because it explicitly checks every possible valid pair. However, if both words appear many times, the number of comparisons can become very large. In the worst case, this can approach quadratic behavior.
Optimal Approach
The key observation is that we do not need to compare every pair of occurrences.
Instead, while scanning the array from left to right, we only need to remember the most recent position where we saw word1 and the most recent position where we saw word2.
Whenever we encounter one of the target words, we update its latest index. If we have already seen the other word before, we immediately compute the current distance and update the minimum answer.
This works because the shortest distance involving the current occurrence must come from the closest previously seen occurrence of the other word. By continuously updating the latest positions, we efficiently track all relevant candidate distances in a single pass.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Store all indices and compare every pair |
| Optimal | O(n) | O(1) | Single pass using latest seen positions |
Algorithm Walkthrough
- Initialize two variables to store the most recent indices of
word1andword2.
These variables start with a sentinel value such as -1 to indicate that the word has not been seen yet.
2. Initialize a variable minimum_distance with a very large value.
This variable will store the smallest distance found so far. 3. Traverse the array from left to right using an index.
At each position, inspect the current word.
4. If the current word matches word1, update the latest index for word1.
After updating, check whether word2 has already been seen. If it has, compute the distance between the two indices and update the minimum if necessary.
5. If the current word matches word2, update the latest index for word2.
After updating, check whether word1 has already been seen. If it has, compute the distance and update the minimum.
6. Continue scanning until the end of the array.
Every time one of the target words appears, we potentially discover a shorter distance. 7. Return the final minimum distance.
Why it works
The algorithm maintains an important invariant throughout the traversal:
index1always stores the most recent occurrence ofword1index2always stores the most recent occurrence ofword2
When we encounter one target word, the closest possible pairing with the other word must involve the most recently seen occurrence of that other word. Older occurrences are always farther away because the traversal proceeds left to right.
Since every occurrence is processed exactly once and every candidate closest pair is evaluated when encountered, the algorithm correctly finds the global minimum distance.
Python Solution
from typing import List
class Solution:
def shortestDistance(
self,
wordsDict: List[str],
word1: str,
word2: str
) -> int:
index1 = -1
index2 = -1
minimum_distance = float("inf")
for i, word in enumerate(wordsDict):
if word == word1:
index1 = i
if index2 != -1:
minimum_distance = min(
minimum_distance,
abs(index1 - index2)
)
elif word == word2:
index2 = i
if index1 != -1:
minimum_distance = min(
minimum_distance,
abs(index1 - index2)
)
return minimum_distance
The implementation follows the exact logic described in the algorithm walkthrough.
The variables index1 and index2 track the latest positions where the two target words were seen. They begin at -1 because neither word has been encountered at the start.
The loop iterates through the array once using enumerate, which provides both the index and the current word.
Whenever word1 is encountered, index1 is updated. If word2 has already appeared earlier, we compute the distance and update the minimum answer.
The same logic applies symmetrically when word2 is encountered.
The use of elif is important because the problem guarantees that word1 and word2 are different. This prevents unnecessary double checking.
Finally, the algorithm returns the smallest distance found during the traversal.
Go Solution
import "math"
func shortestDistance(wordsDict []string, word1 string, word2 string) int {
index1 := -1
index2 := -1
minDistance := math.MaxInt32
for i, word := range wordsDict {
if word == word1 {
index1 = i
if index2 != -1 {
distance := index1 - index2
if distance < 0 {
distance = -distance
}
if distance < minDistance {
minDistance = distance
}
}
} else if word == word2 {
index2 = i
if index1 != -1 {
distance := index1 - index2
if distance < 0 {
distance = -distance
}
if distance < minDistance {
minDistance = distance
}
}
}
}
return minDistance
}
The Go implementation closely mirrors the Python solution. Since Go does not provide a built in absolute value function for integers, we manually convert negative distances to positive values.
The variable minDistance is initialized using math.MaxInt32, which acts as a large initial value.
Slices in Go behave similarly to dynamic arrays, so iterating with range provides both the index and the word efficiently.
No additional memory allocations are needed beyond a few integer variables, preserving the constant space complexity.
Worked Examples
Example 1
Input:
wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
word1 = "coding"
word2 = "practice"
We trace the algorithm step by step.
| Index | Word | index1 ("coding") | index2 ("practice") | Distance | Minimum |
|---|---|---|---|---|---|
| 0 | practice | -1 | 0 | N/A | inf |
| 1 | makes | -1 | 0 | N/A | inf |
| 2 | perfect | -1 | 0 | N/A | inf |
| 3 | coding | 3 | 0 | 3 | 3 |
| 4 | makes | 3 | 0 | N/A | 3 |
Final answer:
3
Example 2
Input:
wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
word1 = "makes"
word2 = "coding"
| Index | Word | index1 ("makes") | index2 ("coding") | Distance | Minimum |
|---|---|---|---|---|---|
| 0 | practice | -1 | -1 | N/A | inf |
| 1 | makes | 1 | -1 | N/A | inf |
| 2 | perfect | 1 | -1 | N/A | inf |
| 3 | coding | 1 | 3 | 2 | 2 |
| 4 | makes | 4 | 3 | 1 | 1 |
Final answer:
1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each word is processed exactly once |
| Space | O(1) | Only a few integer variables are used |
The algorithm performs a single linear scan through the array. Every iteration performs only constant time operations such as comparisons, assignments, and arithmetic.
No auxiliary data structures proportional to the input size are allocated. Therefore, the space usage remains constant regardless of the array length.
Test Cases
from typing import List
class Solution:
def shortestDistance(
self,
wordsDict: List[str],
word1: str,
word2: str
) -> int:
index1 = -1
index2 = -1
minimum_distance = float("inf")
for i, word in enumerate(wordsDict):
if word == word1:
index1 = i
if index2 != -1:
minimum_distance = min(
minimum_distance,
abs(index1 - index2)
)
elif word == word2:
index2 = i
if index1 != -1:
minimum_distance = min(
minimum_distance,
abs(index1 - index2)
)
return minimum_distance
solution = Solution()
assert solution.shortestDistance(
["practice", "makes", "perfect", "coding", "makes"],
"coding",
"practice"
) == 3 # provided example 1
assert solution.shortestDistance(
["practice", "makes", "perfect", "coding", "makes"],
"makes",
"coding"
) == 1 # provided example 2
assert solution.shortestDistance(
["a", "b"],
"a",
"b"
) == 1 # smallest possible valid input
assert solution.shortestDistance(
["a", "x", "x", "x", "b"],
"a",
"b"
) == 4 # words at opposite ends
assert solution.shortestDistance(
["a", "b", "a", "a", "b"],
"a",
"b"
) == 1 # multiple occurrences
assert solution.shortestDistance(
["one", "two", "three", "two", "one"],
"one",
"two"
) == 1 # closest pair not first occurrences
assert solution.shortestDistance(
["x", "y", "z", "x", "y"],
"z",
"y"
) == 1 # closest occurrence after target
assert solution.shortestDistance(
["apple", "banana", "apple", "banana", "apple"],
"apple",
"banana"
) == 1 # alternating pattern
| Test | Why |
|---|---|
["practice", "makes", "perfect", "coding", "makes"] |
Validates provided examples |
["a", "b"] |
Tests smallest valid input size |
["a", "x", "x", "x", "b"] |
Tests words far apart |
["a", "b", "a", "a", "b"] |
Tests repeated occurrences |
["one", "two", "three", "two", "one"] |
Ensures closest pair is correctly identified |
["x", "y", "z", "x", "y"] |
Tests updating nearest indices dynamically |
["apple", "banana", "apple", "banana", "apple"] |
Tests alternating repeated words |
Edge Cases
One important edge case occurs when the two target words appear adjacent to each other. In this situation, the minimum possible valid distance is 1. A buggy implementation might accidentally skip updates or fail to compare consecutive positions correctly. This implementation handles the case naturally because every occurrence immediately computes a distance against the latest occurrence of the other word.
Another important case involves multiple occurrences of both words. A naive implementation might incorrectly compare only the first occurrences or only the last occurrences. For example, in ["a", "b", "a", "b"], the closest distance comes from the middle pair, not necessarily the first pair. The algorithm correctly updates the latest seen indices during traversal, ensuring every relevant pairing is considered.
A third edge case is when the words appear at the extreme ends of the array. For example, ["start", "x", "x", "x", "end"]. Some implementations may contain off by one errors when computing distances near array boundaries. Since this solution uses direct index subtraction with absolute value, it correctly handles words located anywhere in the array.
A final subtle case occurs when one word appears many times before the other word appears for the first time. For example, ["a", "a", "a", "b"]. The algorithm safely delays distance calculations until both indices are initialized. The sentinel value -1 prevents invalid computations before both target words have been encountered.