Shortest Word Distance — Solution in Python, Java & C++
Shortest Word Distance solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Shortest Word Distance is an easy coding problem on arrays, strings and two pointers, asked in Amazon, Meta and Infosys interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Two Pointers
- Asked at: Amazon, Meta, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a list of words and two different words that both appear in it, return the shortest distance between their positions.
Example 1
Input: wordsDict = ["drill","makes","codekairo","kata","makes"], word1 = "kata", word2 = "drill"
Output: 3
Explanation: Indices 3 and 0 are three apart.
Example 2
Input: wordsDict = ["drill","makes","codekairo","kata","makes"], word1 = "makes", word2 = "kata"
Output: 1
Explanation: Indices 4 and 3 are adjacent.
Example 3
Input: wordsDict = ["a","b"], word1 = "a", word2 = "b"
Output: 1
Constraints
2 <= wordsDict.length <= 300001 <= word length <= 10word1 and word2 both appear in wordsDict and differ from each other.
Hints for Shortest Word Distance
Hint 1
One pass is enough: remember the most recent index of each word.
Hint 2
Whenever both have been seen, their current indices give a candidate distance.
Hint 3
The most recent occurrence is always the best partner for the word just encountered.
How to solve Shortest Word Distance
Sweep once, keeping the latest position of each of the two words. Every time either is seen, the pair of latest positions is the closest pairing involving that occurrence.
Approach
- Track
i1andi2, the most recent indices ofword1andword2, both starting unset. - Update the relevant index at each position.
- Once both are set, record
|i1 - i2|and keep the minimum.
Why it works
For an occurrence at index i, the nearest occurrence of the other word to its left is the most recent one — anything earlier is further away. A nearer occurrence on the right will be considered when that position is reached, so scanning once covers every closest pair.
Complexity
- Time —
O(n · L) - Space —
O(1)
Pitfalls
- Collecting all indices of both words and comparing every pair is
O(n²)in the worst case. - Recording a distance before both words have been seen uses an unset index.
- The two words are guaranteed different, which is what makes
|i1 - i2|never zero.
Reference solution
Python
from typing import List
def shortestDistance(wordsDict: List[str], word1: str, word2: str) -> int:
i1 = i2 = -1
best = -1
for i, w in enumerate(wordsDict):
if w == word1:
i1 = i
if w == word2:
i2 = i
if i1 >= 0 and i2 >= 0:
d = abs(i1 - i2)
if best < 0 or d < best:
best = d
return bestJava
public static int shortestDistance(String[] wordsDict, String word1, String word2) {
int i1 = -1, i2 = -1, best = -1;
for (int i = 0; i < wordsDict.length; i++) {
if (wordsDict[i].equals(word1)) i1 = i;
if (wordsDict[i].equals(word2)) i2 = i;
if (i1 >= 0 && i2 >= 0) {
int d = Math.abs(i1 - i2);
if (best < 0 || d < best) best = d;
}
}
return best;
}C++
int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
int i1 = -1, i2 = -1, best = -1;
for (int i = 0; i < (int) wordsDict.size(); i++) {
if (wordsDict[i] == word1) i1 = i;
if (wordsDict[i] == word2) i2 = i;
if (i1 >= 0 && i2 >= 0) {
int d = abs(i1 - i2);
if (best < 0 || d < best) best = d;
}
}
return best;
}JavaScript
var shortestDistance = function(wordsDict, word1, word2) {
var i1 = -1, i2 = -1, best = -1;
for (var i = 0; i < wordsDict.length; i++) {
if (wordsDict[i] === word1) i1 = i;
if (wordsDict[i] === word2) i2 = i;
if (i1 >= 0 && i2 >= 0) {
var d = Math.abs(i1 - i2);
if (best < 0 || d < best) best = d;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.