Shortest Word Distance II

Shortest Word Distance II adds a twist that interviewers love. You get asked the same kind of question many times. So the real test is not one answer. It is how you set things up once so every later question is fast.

🎯 The Problem

You get a list of words and answer shortest-distance queries for pairs of words.

• The distance is how many positions apart their closest copies are.
• You will be asked many times, for different pairs.
• A repeated word appears more than once in the list.
• For a repeated word, use whichever copy gives the smallest gap.

Let us say the list is ["practice", "makes", "perfect", "coding", "makes"]. Ask for the distance between "coding" and "practice". The word coding sits at position 3. The word practice sits at position 0. So the gap is 3.

Input:  words = ["practice", "makes", "perfect", "coding", "makes"]
        query: distance("coding", "makes")
Output: 1

Explanation: coding is at index 3, makes is at index 1 and 4.
The closest makes is at 4, so the distance is 4 - 3 = 1.

Because we get many queries, we want a setup that answers each one quickly.

Here is the idea. Build a map from each word to all the positions where it appears.

🐢 Approach 1: Rescan the List Per Query (Brute Force)

The idea in one line: for each query, walk the whole list and track the closest pair of positions.

The idea:

• Walk the full list on every query.
• Note the latest position of each of the two words.
• Once both are seen, check the gap and keep the smallest.

Why it is weak:

• Each query scans the whole list from the start.
• Many queries means the same scan again and again.
• The repeated full scan gets slow when queries pile up.

Here is the rescan-per-query code:

class WordDistance:
    def __init__(self, words_dict):
        self.words = words_dict

    def shortest(self, word1, word2):
        best = float("inf")
        last1 = last2 = -1
        for i, word in enumerate(self.words):
            if word == word1:
                last1 = i
            if word == word2:
                last2 = i
            if last1 != -1 and last2 != -1:
                best = min(best, abs(last1 - last2))
        return best

⚡ Approach 2: Precompute Index Lists, Two Pointers (Best)

The idea in one line: build a word-to-positions map once, then zip the two position lists with two pointers per query.

The idea:

• Do the heavy work once, in setup.
• A hash map stores a key and a value and looks the key up almost instantly.
• Here the key is a word and the value is its list of positions.

How it works:

• Setup: walk the list once and append each word’s position to its list.
• Each list ends up sorted, since we build left to right.
• A query grabs the two position lists.
• The two pointer idea moves a marker through each sorted list.
• Start a pointer at the front of each. Compare the two positions.
• Record the gap. Then move the pointer at the smaller position forward.
• Stop when one list ends. The smallest gap seen is the answer.

Why moving the smaller one works:

• The smaller position is the one holding the gap open.
• Moving it forward is the only move that can shrink the gap.

Why it is fast:

• Setup is one pass.
• Each query only walks two short lists, not the whole list.
• So repeated queries become cheap.

Here is the two pointer walk for coding at [3] and makes at [1, 4].

Steps to Solve

1. In setup, walk the word list once with each word’s position.
2. For each word, append its position to that word’s list in a hash map.
3. For a query, get the two position lists from the map.
4. Put a pointer at the start of each list.
5. Compare the two positions, record the gap, and move the pointer at the smaller position forward.
6. Stop when one list ends and return the smallest gap seen.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char words[100][50];
int positions[100][100];  // positions[w] holds indexes for word w
int posCount[100];
int wordTotal = 0;

// find a word's slot, creating it if new
int wordSlot(const char* w) {
    for (int i = 0; i < wordTotal; i++) {
        if (strcmp(words[i], w) == 0) return i;
    }
    strcpy(words[wordTotal], w);
    posCount[wordTotal] = 0;
    return wordTotal++;
}

int shortest(const char* a, const char* b) {
    int ia = wordSlot(a), ib = wordSlot(b);
    int i = 0, j = 0, best = 1000000;
    while (i < posCount[ia] && j < posCount[ib]) {
        int pa = positions[ia][i], pb = positions[ib][j];
        int gap = abs(pa - pb);
        if (gap < best) best = gap;
        if (pa < pb) i++;   // move the smaller forward
        else j++;
    }
    return best;
}

int main(void) {
    const char* list[] = {"practice", "makes", "perfect", "coding", "makes"};
    int n = 5;
    for (int k = 0; k < n; k++) {
        int s = wordSlot(list[k]);
        positions[s][posCount[s]++] = k;  // record this position
    }
    printf("%d\n", shortest("coding", "makes"));
    return 0;
}

1

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <cmath>
using namespace std;

class WordDistance {
    unordered_map<string, vector<int>> index;  // word -> positions
public:
    WordDistance(vector<string>& words) {
        for (int i = 0; i < (int)words.size(); i++) {
            index[words[i]].push_back(i);       // record each position
        }
    }

    int shortest(string a, string b) {
        vector<int>& la = index[a];
        vector<int>& lb = index[b];
        int i = 0, j = 0, best = 1e9;
        while (i < (int)la.size() && j < (int)lb.size()) {
            best = min(best, abs(la[i] - lb[j]));
            if (la[i] < lb[j]) i++;   // move the smaller forward
            else j++;
        }
        return best;
    }
};

int main() {
    vector<string> words = {"practice", "makes", "perfect", "coding", "makes"};
    WordDistance wd(words);
    cout << wd.shortest("coding", "makes") << endl;
    return 0;
}

1

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class WordDistance {
    private Map<String, List<Integer>> index = new HashMap<>();  // word -> positions

    public WordDistance(String[] words) {
        for (int i = 0; i < words.length; i++) {
            index.computeIfAbsent(words[i], key -> new ArrayList<>()).add(i);
        }
    }

    public int shortest(String a, String b) {
        List<Integer> la = index.get(a);
        List<Integer> lb = index.get(b);
        int i = 0, j = 0, best = Integer.MAX_VALUE;
        while (i < la.size() && j < lb.size()) {
            int pa = la.get(i), pb = lb.get(j);
            best = Math.min(best, Math.abs(pa - pb));
            if (pa < pb) i++;   // move the smaller forward
            else j++;
        }
        return best;
    }

    public static void main(String[] args) {
        String[] words = { "practice", "makes", "perfect", "coding", "makes" };
        WordDistance wd = new WordDistance(words);
        System.out.println(wd.shortest("coding", "makes"));
    }
}

1

class WordDistance:
    def __init__(self, words):
        self.index = {}                     # word -> list of positions
        for i, word in enumerate(words):
            self.index.setdefault(word, []).append(i)  # record position

    def shortest(self, a, b):
        la = self.index[a]                  # positions of word a
        lb = self.index[b]                  # positions of word b
        i, j = 0, 0
        best = float("inf")
        while i < len(la) and j < len(lb):
            best = min(best, abs(la[i] - lb[j]))
            if la[i] < lb[j]:               # move the smaller forward
                i += 1
            else:
                j += 1
        return best


words = ["practice", "makes", "perfect", "coding", "makes"]
wd = WordDistance(words)
print(wd.shortest("coding", "makes"))

1

class WordDistance {
  constructor(words) {
    this.index = new Map(); // word -> array of positions
    words.forEach((word, i) => {
      if (!this.index.has(word)) this.index.set(word, []);
      this.index.get(word).push(i); // record position
    });
  }

  shortest(a, b) {
    const la = this.index.get(a);
    const lb = this.index.get(b);
    let i = 0;
    let j = 0;
    let best = Infinity;
    while (i < la.length && j < lb.length) {
      best = Math.min(best, Math.abs(la[i] - lb[j]));
      if (la[i] < lb[j]) i++; // move the smaller forward
      else j++;
    }
    return best;
  }
}

const words = ["practice", "makes", "perfect", "coding", "makes"];
const wd = new WordDistance(words);
console.log(wd.shortest("coding", "makes"));

1

Let us walk through the Python version line by line, so the two pointer part is clear.

The method __init__ runs once when we build the object. The line self.index = {} makes an empty dictionary. The loop for i, word in enumerate(words): reads each word with its position. Then self.index.setdefault(word, []).append(i) does the work. The setdefault(word, []) returns the word’s list, making an empty one if the word is new. Then append(i) adds this position. So after the loop, each word maps to all its positions in order.

The method shortest answers one query. The lines la = self.index[a] and lb = self.index[b] grab the two position lists. Both are already sorted because we built them from left to right.

The lines i, j = 0, 0 start a pointer at the front of each list. The line best = float("inf") starts the best gap as infinity, so any real gap will be smaller.

The loop while i < len(la) and j < len(lb): runs while both lists still have positions. The line best = min(best, abs(la[i] - lb[j])) checks the gap between the two current positions and keeps the smaller value. The abs makes the gap positive no matter which word comes first.

The check if la[i] < lb[j]: decides which pointer to move. We move the one at the smaller position forward. That is the only move that can shrink the gap, because the smaller position is the one holding us back. When one list runs out, we stop and return the best gap.

⏱️ Time and Space Complexity

The setup walks the word list once, so it is O(n) time and O(n) space, where n is how many words there are. Each query only walks the two position lists. So a query costs about O(a + b), where a and b are how many times those two words appear. The brute force instead rescans all n words on every query, which gets expensive when there are many queries.

🧩 Key Takeaways

• ✅ When you get many queries, do the heavy work once in setup.
• ✅ Map each word to the sorted list of positions where it appears.
• ✅ A query walks the two position lists with two pointers.
• ✅ Move the pointer at the smaller position, because that is the only way the gap can shrink.
• ✅ Setup is O(n), and each query only touches its two short lists.

🚀 What’s Next?

• Subdomain Visit Count
• Top K Frequent Elements