Shortest Word Distance
Asked at Snowflake
Problem
Shortest Word Distance gives you a list of words and two different words that both appear in it, and asks for the smallest distance between an occurrence of the first and an occurrence of the second. It rewards a clean one-pass scan instead of comparing every pair of positions.
Asked At
| Company | Difficulty | |
|---|---|---|
| Snowflake | Easy | View all Snowflake questions → |
How to Think About It
Brute force: collect all indices of word1 and all indices of word2, then compare every pair. That is O(a * b) in the worst case.
Key insight: when you reach an occurrence of one word, the only occurrence of the other word that can give the best distance "so far" is the most recent one. So remember just the last index of each.
Scan once. When you see word1, update i1; when you see word2, update i2. Whenever both are set, update best = min(best, abs(i1 - i2)).
Walkthrough for ["practice","makes","perfect","coding","makes"], "coding", "practice": index 0 sets practice=0; index 3 sets coding=3 -> distance 3. Answer 3.
Edge cases: the words are guaranteed to be different and both present. The follow-ups are the interesting part — many queries (Shortest Word Distance II) and word1 == word2 (III).
Optimal Approach
Step 1: i1 = i2 = -1, best = infinity.
Step 2: For each index i:
If words[i] == word1: i1 = i.
If words[i] == word2: i2 = i.
If both i1 and i2 are set: best = min(best, abs(i1 - i2)).
Step 3: Return best.
Time: O(n) comparisons (each is O(L) for word length). Space: O(1).
What Trips People Up in Real Interviews
Storing every index and comparing all pairs. It is correct but quadratic — the "last seen" trick is what the interviewer is waiting for.
Only computing the distance when you see word2. You must update after either word, because the closest pair can end on either one.
Not asking about follow-ups. Mention that for many queries you would preprocess index lists (Shortest Word Distance II).
Initializing best to 0 instead of a large value.
Solution Code
def shortestDistance(wordsDict, word1, word2):
i1 = i2 = -1
best = len(wordsDict)
for i, w in enumerate(wordsDict):
if w == word1:
i1 = i
elif w == word2:
i2 = i
if i1 != -1 and i2 != -1:
best = min(best, abs(i1 - i2))
return bestFrequently Asked Questions
What is the Shortest Word Distance problem?
Shortest Word Distance gives you a list of words and two different words that both appear in it, and asks for the smallest distance between an occurrence of the first and an occurrence of the second. It rewards a clean one-pass scan instead of comparing every pair of positions.
How do you solve Shortest Word Distance?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Shortest Word Distance?
Shortest Word Distance is asked at Snowflake. It is a easy difficulty problem.
What are common mistakes on Shortest Word Distance?
- Storing every index and comparing all pairs. It is correct but quadratic — the "last seen" trick is what the interviewer is waiting for.
- Only computing the distance when you see `word2`. You must update after either word, because the closest pair can end on either one.
- Not asking about follow-ups. Mention that for many queries you would preprocess index lists (Shortest Word Distance II).
- Initializing `best` to 0 instead of a large value.