Shortest Word Distance II
Shortest Word Distance II is a medium design data structures problem solved with the pre-processing + tradeoffs pattern.
The best approach, optimal (index lists + two-pointer merge), runs in O(n) build, O(p + q) per query time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan the array per query) up.
Problem
Design a structure that is built once from an array of strings wordsDict and then answers many questions of the form: what is the smallest distance between a position holding word1 and a position holding word2?
WordDistance(wordsDict)stores the array.shortest(word1, word2)returns the minimum of|i - j|over all indices withwordsDict[i] == word1andwordsDict[j] == word2.
Both words are guaranteed to be in the array, and they are different words. Words may appear many times.
Examples
Example 1
- Input
WordDistance(["red", "blue", "green", "red", "yellow", "blue"]), shortest("red", "blue"), shortest("green", "yellow"), shortest("yellow", "red")- Output
1, 2, 1- Why
- "red" at 0 and "blue" at 1 are adjacent; "green" (2) and "yellow" (4) are 2 apart; "yellow" (4) is next to the second "red" (3).
Example 2
- Input
WordDistance(["sun", "moon", "star", "moon", "sun"]), shortest("sun", "star"), shortest("moon", "sun")- Output
2, 1- Why
- "star" at 2 is 2 away from both copies of "sun"; the "moon" at 3 touches the "sun" at 4.
Constraints
1 <= wordsDict.length <= 3 * 10^41 <= wordsDict[i].length <= 10, lowercase English letters.word1andword2are both inwordsDictandword1 != word2.- At most
5000calls are made toshortest.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan the array per query) | O(n) per query | O(1) extra |
| Optimal (index lists + two-pointer merge) | O(n) build, O(p + q) per query | O(n) |
1Brute force (scan the array per query)
O(n) per queryEvery query rescans all n words.O(1) extraOnly two indices and the best distance, besides the stored array.Store the array. For each query, walk it once, remembering the most recent index of word1 and of word2, and update the best distance whenever one of them is seen.
- Constructor: keep a reference to wordsDict.
- shortest: i1 = i2 = -1, best = infinity.
- For each index k: if the word is word1 set i1 = k, if it is word2 set i2 = k; when both are set, best = min(best, |i1 - i2|).
class WordDistance {
private final String[] words;
public WordDistance(String[] wordsDict) {
words = wordsDict;
}
public int shortest(String word1, String word2) {
int i1 = -1, i2 = -1, best = Integer.MAX_VALUE;
for (int k = 0; k < words.length; k++) {
if (words[k].equals(word1)) i1 = k;
else if (words[k].equals(word2)) i2 = k;
if (i1 != -1 && i2 != -1) best = Math.min(best, Math.abs(i1 - i2));
}
return best;
}
}class WordDistance:
def __init__(self, wordsDict: List[str]):
self.words = wordsDict
def shortest(self, word1: str, word2: str) -> int:
i1 = i2 = -1
best = float("inf")
for k, w in enumerate(self.words):
if w == word1:
i1 = k
elif w == word2:
i2 = k
if i1 != -1 and i2 != -1:
best = min(best, abs(i1 - i2))
return bestclass WordDistance {
vector<string> words;
public:
WordDistance(vector<string>& wordsDict) : words(wordsDict) {}
int shortest(string word1, string word2) {
int i1 = -1, i2 = -1, best = INT_MAX;
for (int k = 0; k < (int)words.size(); k++) {
if (words[k] == word1) i1 = k;
else if (words[k] == word2) i2 = k;
if (i1 != -1 && i2 != -1) best = min(best, abs(i1 - i2));
}
return best;
}
};class WordDistance {
constructor(wordsDict) {
this.words = wordsDict;
}
shortest(word1, word2) {
let i1 = -1, i2 = -1, best = Infinity;
for (let k = 0; k < this.words.length; k++) {
if (this.words[k] === word1) i1 = k;
else if (this.words[k] === word2) i2 = k;
if (i1 !== -1 && i2 !== -1) best = Math.min(best, Math.abs(i1 - i2));
}
return best;
}
}2Optimal (index lists + two-pointer merge)
O(n) build, O(p + q) per queryBuilding visits each word once; a query walks only the p and q occurrences of the two words.O(n)Every index is stored exactly once across all lists.In the constructor, map each word to the increasing list of positions where it occurs. A query then only looks at the positions of the two words: walk both sorted lists with two pointers, record the gap between the current pair, and advance the pointer at the smaller position, because moving the larger one can only widen the gap.
- Constructor: for k in 0..n-1, append k to positions[wordsDict[k]].
- shortest: a = positions[word1], b = positions[word2], i = j = 0.
- While both pointers are in range: best = min(best, |a[i] - b[j]|); advance i if a[i] < b[j], otherwise advance j.
- Return best.
class WordDistance {
private final Map<String, List<Integer>> positions = new HashMap<>();
public WordDistance(String[] wordsDict) {
for (int k = 0; k < wordsDict.length; k++) {
positions.computeIfAbsent(wordsDict[k], w -> new ArrayList<>()).add(k);
}
}
public int shortest(String word1, String word2) {
List<Integer> a = positions.get(word1), b = positions.get(word2);
int i = 0, j = 0, best = Integer.MAX_VALUE;
while (i < a.size() && j < b.size()) {
int x = a.get(i), y = b.get(j);
best = Math.min(best, Math.abs(x - y));
if (x < y) i++;
else j++;
}
return best;
}
}class WordDistance:
def __init__(self, wordsDict: List[str]):
self.positions = {}
for k, w in enumerate(wordsDict):
self.positions.setdefault(w, []).append(k)
def shortest(self, word1: str, word2: str) -> int:
a, b = self.positions[word1], self.positions[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 bestclass WordDistance {
unordered_map<string, vector<int>> positions;
public:
WordDistance(vector<string>& wordsDict) {
for (int k = 0; k < (int)wordsDict.size(); k++) positions[wordsDict[k]].push_back(k);
}
int shortest(string word1, string word2) {
const vector<int>& a = positions[word1];
const vector<int>& b = positions[word2];
int i = 0, j = 0, best = INT_MAX;
while (i < (int)a.size() && j < (int)b.size()) {
best = min(best, abs(a[i] - b[j]));
if (a[i] < b[j]) i++;
else j++;
}
return best;
}
};class WordDistance {
constructor(wordsDict) {
this.positions = new Map();
wordsDict.forEach((w, k) => {
if (!this.positions.has(w)) this.positions.set(w, []);
this.positions.get(w).push(k);
});
}
shortest(word1, word2) {
const a = this.positions.get(word1), b = this.positions.get(word2);
let i = 0, j = 0, best = Infinity;
while (i < a.length && j < b.length) {
best = Math.min(best, Math.abs(a[i] - b[j]));
if (a[i] < b[j]) i++;
else j++;
}
return best;
}
}Edge cases to test
- The two words are adjacent: the answer is 1
- Words that appear many times, where the closest pair is not the first occurrences
- The same pair queried repeatedly
- Arguments given in either order
Hints
Hint 1
A single query is easy: scan the array and remember the latest index of each word. Why is that wasteful when there are thousands of queries?
Hint 2
Preprocess once: map every word to the sorted list of indices where it appears.
Hint 3
For a query, merge the two sorted index lists with two pointers, always advancing the pointer at the smaller index.
FAQ
What is the best time complexity for Shortest Word Distance II?
Optimal (index lists + two-pointer merge) runs in O(n) build, O(p + q) per query time and O(n) extra space. Building visits each word once; a query walks only the p and q occurrences of the two words.
Which pattern does Shortest Word Distance II use?
It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.
Is there a brute force solution for Shortest Word Distance II?
Yes. Brute force (scan the array per query) takes O(n) per query time and O(1) extra space. Store the array.
Which edge cases should I test for Shortest Word Distance II?
The two words are adjacent: the answer is 1; Words that appear many times, where the closest pair is not the first occurrences; The same pair queried repeatedly; Arguments given in either order.