Shortest Word Distance II

medium design hash map two pointers

Problem

Design a class that takes a list of words at construction and supports repeated queries of the shortest distance between any two distinct words.

InputwordsDict = ["practice","makes","perfect","coding","makes"]; shortest("coding","practice")

Output3

positions: practice=[0], coding=[3]. Merge → min |3−0| = 3.

words (comma-separated)

word1

word2

class WordDistance:
    def __init__(self, words):
        self.idx = {}
        for i, w in enumerate(words):
            self.idx.setdefault(w, []).append(i)

    def shortest(self, w1, w2):
        a, b = self.idx[w1], self.idx[w2]
        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 best

class WordDistance {
  constructor(words) {
    this.idx = new Map();
    words.forEach((w, i) => {
      if (!this.idx.has(w)) this.idx.set(w, []);
      this.idx.get(w).push(i);
    });
  }
  shortest(w1, w2) {
    const a = this.idx.get(w1), b = this.idx.get(w2);
    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;
  }
}

class WordDistance {
    Map> idx = new HashMap<>();
    public WordDistance(String[] words) {
        for (int i = 0; i < words.length; i++)
            idx.computeIfAbsent(words[i], k -> new ArrayList<>()).add(i);
    }
    public int shortest(String w1, String w2) {
        List a = idx.get(w1), b = idx.get(w2);
        int i = 0, j = 0, best = Integer.MAX_VALUE;
        while (i < a.size() && j < b.size()) {
            best = Math.min(best, Math.abs(a.get(i) - b.get(j)));
            if (a.get(i) < b.get(j)) i++; else j++;
        }
        return best;
    }
}

class WordDistance {
    unordered_map> idx;
public:
    WordDistance(vector& words) {
        for (int i = 0; i < (int)words.size(); i++) idx[words[i]].push_back(i);
    }
    int shortest(string w1, string w2) {
        auto& a = idx[w1]; auto& b = idx[w2];
        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;
    }
};

Explanation

Because the same two words may be queried many times, we do the heavy lifting once at construction: we record, for every word, the sorted list of positions where it appears in the input.

For a query, we grab the two position lists a and b and find the closest pair of positions using a two-pointer merge. We compare a[i] and b[j], update best with their distance, then advance whichever pointer points at the smaller position.

Advancing the smaller side is the key insight: moving it is the only way the gap can shrink, so we never miss the true minimum, and each list is scanned just once.

Example: idx["coding"] = [3] and idx["practice"] = [0]. The single comparison gives |3 - 0| = 3, so shortest("coding", "practice") returns 3.

Time: O(m + n) per query, O(N) build Space: O(N)