Skip to main content

244. Shortest Word Distance II

mediumAsked at LinkedIn

Same as Shortest Word Distance but with many queries. LinkedIn asks this to test whether you can amortize cost across queries — pre-bucket indices by word, then run a merge-like two-pointer walk per query.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in LinkedIn loops.

  • Glassdoor (2026-Q1)— LinkedIn onsite reports list II as a frequent follow-up after the I variant.
  • Blind (2025-11)— LinkedIn writeups specifically call out the multi-query design as the signal — does the candidate amortize?

Problem

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array. Implement the WordDistance class: WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict; int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Constraints

  • 1 <= wordsDict.length <= 3 * 10^4
  • 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

Example 1

Input
["WordDistance", "shortest", "shortest"] [[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]

Approaches

1. Naive: re-scan on every query

Store the list. On each query, walk the list with two index trackers (the I solution).

Time
init O(1), shortest O(n) per query
Space
O(n)
class WordDistanceNaive {
  constructor(wordsDict) { this.words = wordsDict; }
  shortest(word1, word2) {
    let i1 = -1, i2 = -1, best = Infinity;
    for (let i = 0; i < this.words.length; i++) {
      if (this.words[i] === word1) i1 = i;
      else if (this.words[i] === word2) i2 = i;
      if (i1 !== -1 && i2 !== -1) best = Math.min(best, Math.abs(i1 - i2));
    }
    return best;
  }
}

Tradeoff: Correct but at 5000 queries * 3 * 10^4 list size = 1.5 * 10^8 ops worst case, borderline TLE. Mention it then move to the precomputed version.

2. Precompute index lists + merge-walk (optimal)

At init, bucket indices by word into a map. Per query, use two pointers walking sorted index lists for word1 and word2 — advance whichever pointer's index is smaller.

Time
init O(n), shortest O(a + b)
Space
O(n)
class WordDistance {
  constructor(wordsDict) {
    this.idx = new Map();
    for (let i = 0; i < wordsDict.length; i++) {
      if (!this.idx.has(wordsDict[i])) this.idx.set(wordsDict[i], []);
      this.idx.get(wordsDict[i]).push(i);
    }
  }
  shortest(word1, word2) {
    const a = this.idx.get(word1);
    const b = this.idx.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;
  }
}

Tradeoff: Amortized cost across queries — O(a + b) per query where a, b are the per-word counts. The merge-walk is correct because both lists are naturally sorted (insertion order = increasing index).

LinkedIn-specific tips

LinkedIn interviewers specifically want the amortization explanation: 'init pays O(n) once; each query is O(a + b) — far smaller than re-scanning O(n) each time.' Be ready for the related design follow-up: 'What if the words could be added incrementally?' (Same map, just append to the per-word list when a new word arrives.)

Common mistakes

  • Sorting the per-word index lists at init — unnecessary, they're already sorted by construction.
  • Doing a double-for-loop on the index lists (O(a * b)) instead of two-pointer (O(a + b)).
  • Forgetting that advancing the SMALLER-index pointer is what guarantees you visit every potentially-closest pair.

Follow-up questions

An interviewer at LinkedIn may pivot to one of these next:

  • Shortest Word Distance III (LC 245) — word1 might equal word2.
  • What if queries could ask for the kth-shortest? (Min-heap of candidate pairs.)
  • What if the corpus were huge (TB scale)? (Hash + bucket by word; per-query you fetch only the relevant index lists.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is two-pointer better than a double loop on the index lists?

Because for sorted lists, the closest pair always involves either the current a[i] or the current b[j] — once a[i] < b[j], advancing i is safe because no later pairing of a[i] with any b[j+k] can be closer than a[i] with b[j] (which we already considered).

Does the per-word list need to be sorted?

It's already sorted naturally because we insert indices in increasing order during construction. No sort cost.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Shortest Word Distance II and other LinkedIn interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →