Shortest Word Distance

easy array two pointers

Problem

Given a list of words and two distinct words word1 and word2, return the shortest distance between these two words in the list.

InputwordsDict = ["practice","makes","perfect","coding","makes"], word1 = "coding", word2 = "practice"

Output3

indices: coding=3, practice=0 → |3−0| = 3.

words (comma-separated)

word1

word2

def shortest_distance(words, w1, w2):
    i1 = i2 = -1
    best = len(words)
    for i, w in enumerate(words):
        if w == w1: i1 = i
        elif w == w2: i2 = i
        if i1 != -1 and i2 != -1:
            best = min(best, abs(i1 - i2))
    return best

function shortestDistance(words, w1, w2) {
  let i1 = -1, i2 = -1, best = words.length;
  for (let i = 0; i < words.length; i++) {
    if (words[i] === w1) i1 = i;
    else if (words[i] === w2) i2 = i;
    if (i1 !== -1 && i2 !== -1) best = Math.min(best, Math.abs(i1 - i2));
  }
  return best;
}

class Solution {
    public int shortestDistance(String[] words, String w1, String w2) {
        int i1 = -1, i2 = -1, best = words.length;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(w1)) i1 = i;
            else if (words[i].equals(w2)) i2 = i;
            if (i1 != -1 && i2 != -1) best = Math.min(best, Math.abs(i1 - i2));
        }
        return best;
    }
}

int shortestDistance(vector& words, string w1, string w2) {
    int i1 = -1, i2 = -1, best = (int)words.size();
    for (int i = 0; i < (int)words.size(); i++) {
        if (words[i] == w1) i1 = i;
        else if (words[i] == w2) i2 = i;
        if (i1 != -1 && i2 != -1) best = min(best, abs(i1 - i2));
    }
    return best;
}

Explanation

The goal is to find the smallest gap between any spot where word1 appears and any spot where word2 appears. Instead of comparing every pair of positions, we make just one pass through the list.

As we walk, we keep two memories: i1 is the most recent index where we saw word1, and i2 is the most recent index for word2. Both start at -1 to mean "not seen yet".

Whenever the current word matches one of them, we update that index. Then, if both have been seen at least once, we compute the distance abs(i1 - i2) and keep the smallest one in best.

Using the latest index of each word is the key trick: the closest match always involves the most recent occurrence, so we never need to look back at older ones.

Example: ["practice","makes","perfect","coding","makes"] with word1="coding", word2="practice". We record practice at index 0, then coding at index 3. Now both are seen, so abs(3 - 0) = 3, and the answer is 3.

Time: O(n) Space: O(1)