Shortest Word Distance III solution and explanation
4 more videos on this problem
Shortest Word Distance III - Python - LeetCode 245Code with Carter · 10:20 · 1K views
245. Shortest Word Distance III - Week 1/5 Leetcode April ChallengeProgramming Live with Larry · 7:59 · 334 views
Shortest Word Distance III (Medium), C++, LeetcodeH William Polenz · 12:18 · 178 views
Baozi Training Leetcode 245 solution: Shortest Word DistanceBaozi Training · 3:39 · 157 views
LeetCode 245: Shortest Word Distance IIIAlitaCode · 25:16 · 1 view
The problem
Given an array of strings wordsDict and two strings that already exist in the array word1 and word2, return the shortest distance between the occurrence of these two words in the list.
Note that word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list.
Example 1:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1
Example 2:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes" Output: 3
Constraints:
1 <= wordsDict.length <= 1051 <= wordsDict[i].length <= 10wordsDict[i]consists of lowercase English letters.word1andword2are inwordsDict.
Approach overview
Problem Overview: You are given an array of words and two target strings word1 and word2. The task is to compute the smallest index distance between occurrences of these words in the list. The twist: word1 and word2 can be the same, which changes how distances must be calculated.
Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)
Scan the array and record every index where word1 and word2 appear. Then compare every valid pair and compute the absolute index difference. If the words are different, compare indices from both sets. If the words are the same, compare consecutive occurrences to avoid zero distance from the same index. This method is straightforward but inefficient because it checks many unnecessary pairs, making it quadratic in the worst case.
Approach 2: Single Pass Case Analysis (O(n) time, O(1) space)
Traverse the array once while tracking the most recent positions of the target words. Maintain two variables such as idx1 and idx2. When you encounter word1, update idx1; when you encounter word2, update idx2. After each update, compute abs(idx1 - idx2) and update the minimum distance.
The key insight appears when word1 == word2. Instead of keeping two independent indices, treat the current occurrence as the next candidate and compute the distance from the previous occurrence of the same word. Practically, you store the previous index and update the minimum whenever the word appears again. This prevents comparing the same index with itself while still capturing the closest pair.
This approach works because the closest distance must occur between two nearby occurrences in the traversal order. By updating indices during iteration, you avoid storing extra data structures and achieve linear time.
Problems like this frequently appear in interviews that test efficient scanning and state tracking over arrays. The technique is closely related to patterns used in array traversal and string processing problems, where maintaining the last seen index enables constant-time updates.
Recommended for interviews: The single-pass case analysis solution is the expected answer. It demonstrates you can reason about edge cases like identical words while maintaining O(n) efficiency. Mentioning the brute force approach first shows baseline understanding, but implementing the linear scan with correct handling for word1 == word2 shows strong problem-solving ability.
Solution
First, we check whether word1 and word2 are equal:
- If they are equal, iterate through the array
wordsDictto find two indicesiandjofword1, and compute the minimum value ofi-j. - If they are not equal, iterate through the array
wordsDictto find the indicesiofword1andjofword2, and compute the minimum value ofi-j.
The time complexity is O(n), where n is the length of the array wordsDict. The space complexity is O(1).
class Solution:
def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
ans = len(wordsDict)
if word1 == word2:
j = -1
for i, w in enumerate(wordsDict):
if w == word1:
if j != -1:
ans = min(ans, i - j)
j = i
else:
i = j = -1
for k, w in enumerate(wordsDict):
if w == word1:
i = k
if w == word2:
j = k
if i != -1 and j != -1:
ans = min(ans, abs(i - j))
return ansclass Solution {
public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
int ans = wordsDict.length;
if (word1.equals(word2)) {
for (int i = 0, j = -1; i < wordsDict.length; ++i) {
if (wordsDict[i].equals(word1)) {
if (j != -1) {
ans = Math.min(ans, i - j);
}
j = i;
}
}
} else {
for (int k = 0, i = -1, j = -1; k < wordsDict.length; ++k) {
if (wordsDict[k].equals(word1)) {
i = k;
}
if (wordsDict[k].equals(word2)) {
j = k;
}
if (i != -1 && j != -1) {
ans = Math.min(ans, Math.abs(i - j));
}
}
}
return ans;
}
}class Solution {
public:
int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
int n = wordsDict.size();
int ans = n;
if (word1 == word2) {
for (int i = 0, j = -1; i < n; ++i) {
if (wordsDict[i] == word1) {
if (j != -1) {
ans = min(ans, i - j);
}
j = i;
}
}
} else {
for (int k = 0, i = -1, j = -1; k < n; ++k) {
if (wordsDict[k] == word1) {
i = k;
}
if (wordsDict[k] == word2) {
j = k;
}
if (i != -1 && j != -1) {
ans = min(ans, abs(i - j));
}
}
}
return ans;
}
};function shortestWordDistance(wordsDict: string[], word1: string, word2: string): number {
let ans = wordsDict.length;
if (word1 === word2) {
let j = -1;
for (let i = 0; i < wordsDict.length; i++) {
if (wordsDict[i] === word1) {
if (j !== -1) {
ans = Math.min(ans, i - j);
}
j = i;
}
}
} else {
let i = -1,
j = -1;
for (let k = 0; k < wordsDict.length; k++) {
if (wordsDict[k] === word1) {
i = k;
}
if (wordsDict[k] === word2) {
j = k;
}
if (i !== -1 && j !== -1) {
ans = Math.min(ans, Math.abs(i - j));
}
}
}
return ans;
}func shortestWordDistance(wordsDict []string, word1 string, word2 string) int {
ans := len(wordsDict)
if word1 == word2 {
j := -1
for i, w := range wordsDict {
if w == word1 {
if j != -1 {
ans = min(ans, i-j)
}
j = i
}
}
} else {
i, j := -1, -1
for k, w := range wordsDict {
if w == word1 {
i = k
}
if w == word2 {
j = k
}
if i != -1 && j != -1 {
ans = min(ans, abs(i-j))
}
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Useful for understanding the problem or when the array size is extremely small. |
| Index List + Pair Scan | O(n + k²) | O(k) | When you want clearer separation of word positions before computing distances. |
| Single Pass Case Analysis | O(n) | O(1) | Best general solution for interviews and large inputs. |
Frequently asked questions
Is Shortest Word Distance III easy or hard?
Shortest Word Distance III is generally classified as a medium difficulty problem. The challenge comes from handling the case where both target words are the same while still computing the correct minimum distance in a single pass.
Shortest Word Distance III Python/Java solution
Most implementations follow the same logic across languages: iterate once, update the latest indices for the target words, and maintain the minimum distance. The algorithm translates directly into Python, Java, C++, Go, or TypeScript with identical O(n) time complexity.
How to solve Shortest Word Distance III in O(n)?
Iterate through the word list while keeping track of the last index where each target word appeared. When you encounter either word, update its index and compute the distance to the other index. If both target words are identical, track the previous occurrence and compute the distance between consecutive appearances. This maintains a running minimum in linear time.
What is the best approach for Shortest Word Distance III?
The best approach is a single-pass scan that tracks the most recent indices of the target words. Update the index whenever a word appears and compute the absolute difference between indices. A small modification handles the case when both target words are the same. This solution runs in O(n) time and O(1) space.
Is Shortest Word Distance III asked at Google/Amazon/Meta?
Variants of the Shortest Word Distance problems have appeared in interviews at companies like Google, Amazon, and Meta. They test efficient array traversal, handling edge cases, and reasoning about index distances. Interviewers expect the O(n) single-pass solution.
What data structure is used in Shortest Word Distance III?
The optimal solution mainly uses simple integer variables to track the last seen positions of words during array traversal. No complex data structures are required, though the problem conceptually relies on array scanning and index tracking.
What is the time complexity of Shortest Word Distance III?
The optimal solution runs in O(n) time where n is the number of words in the array. Each element is visited exactly once while maintaining the last seen indices. Space complexity is O(1) because only a few integer variables are stored.