244. Shortest Word Distance II
Asked at LinkedIn
Difficulty
Medium
Time
O(n) to build, O(a + b) per quer
Space
O(n)
Pattern
Array
Companies
1
Problem
Design a class that is built once from an array of words, then answers many queries. Each query gives two different words that both appear in the array, and you must return the shortest distance between them.
Distance means the absolute difference between two indices in the array. So if word1 sits at index i and word2 sits at index j, the distance is |i - j|. A word may appear more than once, so you must consider every pair of positions and return the smallest gap.
The class has two parts: a constructor WordDistance(wordsDict) that stores the array, and a method shortest(word1, word2) that returns the answer. Because shortest can be called up to 5000 times, do the heavy work once in the constructor and keep each query fast.
Find the closest pair of indices
Constraints
- ●
1 <= wordsDict.length <= 3 * 10^4 - ●
1 <= wordsDict[i].length <= 10 - ●
wordsDict[i] consists of lowercase English letters - ●
word1 and word2 are in wordsDict - ●
word1 != word2 - ●
At most 5000 calls will be made to shortest
Examples
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]][null, 3, 1]wordsDict = ["a", "b", "a", "c"], shortest("a", "c")1Asked At
1 companies| 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).
Two pointers over sorted index lists
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
O(n) to build, O(a + b) per quer timefrom 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 runs in O(n) to build, O(a + b) per quer time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.