Shortest Word Distance II

Medium Design Data Structures Pre-processing + tradeoffs Original on LeetCode

Reported atLinkedInPalantir

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 with wordsDict[i] == word1 and wordsDict[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^4
  • 1 <= wordsDict[i].length <= 10, lowercase English letters.
  • word1 and word2 are both in wordsDict and word1 != word2.
  • At most 5000 calls are made to shortest.

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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (scan the array per query)O(n) per queryO(1) extra
Optimal (index lists + two-pointer merge)O(n) build, O(p + q) per queryO(n)

1Brute force (scan the array per query)

TimeO(n) per queryEvery query rescans all n words.
SpaceO(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.

  1. Constructor: keep a reference to wordsDict.
  2. shortest: i1 = i2 = -1, best = infinity.
  3. 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;
    }
}

2Optimal (index lists + two-pointer merge)

TimeO(n) build, O(p + q) per queryBuilding visits each word once; a query walks only the p and q occurrences of the two words.
SpaceO(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.

  1. Constructor: for k in 0..n-1, append k to positions[wordsDict[k]].
  2. shortest: a = positions[word1], b = positions[word2], i = j = 0.
  3. While both pointers are in range: best = min(best, |a[i] - b[j]|); advance i if a[i] < b[j], otherwise advance j.
  4. 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;
    }
}

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.