Shortest Word Distance II
Asked at LinkedIn
Problem
Shortest Word Distance II asks you to design a class that is built once from a list of words and then answers many queries of the form "what is the shortest distance between word1 and word2?". It is a design follow-up: spend preprocessing time so each query is fast.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all LinkedIn questions → |
How to Think About It
Rescanning the whole list per query costs O(n) each time. With many queries you want to pay that once.
Key insight: in the constructor, build a map from each word to the sorted list of indices where it appears. Indices are added in increasing order, so the lists are already sorted.
For a query, you have two sorted lists. Walk them with two pointers, like merging: compare the current pair, record the distance, then advance the pointer at the smaller index — advancing the larger one can only increase the gap.
Walkthrough: "makes" -> [1, 4], "coding" -> [3]. Pointers at 1 and 3 -> distance 2, advance the 1 -> 4 and 3 -> distance 1, advance 3 -> done. Answer 1.
Optional optimization: cache answers for repeated (word1, word2) pairs if the interviewer says queries repeat.
Optimal Approach
Constructor: for each index i, append i to pos[words[i]].
Query shortest(word1, word2):
Step 1: a = pos[word1], b = pos[word2], i = j = 0, best = infinity.
Step 2: While i < len(a) and j < len(b):
best = min(best, abs(a[i] - b[j]))
If a[i] < b[j]: i += 1, else j += 1.
Step 3: Return best.
Time: O(n) to build, O(a + b) per query. Space: O(n).
What Trips People Up in Real Interviews
Comparing every pair of indices per query. That is O(a * b); the two-pointer merge is linear in the two list sizes.
Advancing the wrong pointer. Always move the smaller index forward — it is the only move that can shrink the gap.
Rescanning the word list in shortest. The whole point of the design is to do that work once in the constructor.
Forgetting that index lists are naturally sorted when built left to right — no extra sort is needed.
Solution Code
from collections import defaultdict
class WordDistance:
def __init__(self, wordsDict):
self.pos = defaultdict(list)
for i, w in enumerate(wordsDict):
self.pos[w].append(i)
def shortest(self, word1, word2):
a, b = self.pos[word1], self.pos[word2]
i = j = 0
best = float('inf')
while i < len(a) and j < len(b):
best = min(best, abs(a[i] - b[j]))
if a[i] < b[j]:
i += 1
else:
j += 1
return bestFrequently Asked Questions
What is the Shortest Word Distance II problem?
Shortest Word Distance II asks you to design a class that is built once from a list of words and then answers many queries of the form "what is the shortest distance between `word1` and `word2`?". It is a design follow-up: spend preprocessing time so each query is fast.
How do you solve Shortest Word Distance II?
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 II?
Shortest Word Distance II is asked at LinkedIn. It is a medium difficulty problem.
What are common mistakes on Shortest Word Distance II?
- Comparing every pair of indices per query. That is `O(a * b)`; the two-pointer merge is linear in the two list sizes.
- Advancing the wrong pointer. Always move the smaller index forward — it is the only move that can shrink the gap.
- Rescanning the word list in `shortest`. The whole point of the design is to do that work once in the constructor.
- Forgetting that index lists are naturally sorted when built left to right — no extra sort is needed.