Shortest Word Distance — Easy Problem & Solution

Problem statement

Given a list of words and two different words that both appear in it, return the shortest distance between their positions.

Example 1

Input: wordsDict = ["drill","makes","codekairo","kata","makes"], word1 = "kata", word2 = "drill"
Output: 3
Explanation: Indices 3 and 0 are three apart.

Example 2

Input: wordsDict = ["drill","makes","codekairo","kata","makes"], word1 = "makes", word2 = "kata"
Output: 1
Explanation: Indices 4 and 3 are adjacent.

Example 3

Input: wordsDict = ["a","b"], word1 = "a", word2 = "b"
Output: 1

Constraints

• 2 <= wordsDict.length <= 30000
• 1 <= word length <= 10
• word1 and word2 both appear in wordsDict and differ from each other.

How to solve Shortest Word Distance

Sweep once, keeping the latest position of each of the two words. Every time either is seen, the pair of latest positions is the closest pairing involving that occurrence.

Approach

1. Track i1 and i2, the most recent indices of word1 and word2, both starting unset.
2. Update the relevant index at each position.
3. Once both are set, record |i1 - i2| and keep the minimum.

Why it works

For an occurrence at index i, the nearest occurrence of the other word to its left is the most recent one — anything earlier is further away. A nearer occurrence on the right will be considered when that position is reached, so scanning once covers every closest pair.

Complexity

• Time — O(n · L)
• Space — O(1)

Pitfalls

• Collecting all indices of both words and comparing every pair is O(n²) in the worst case.
• Recording a distance before both words have been seen uses an unset index.
• The two words are guaranteed different, which is what makes |i1 - i2| never zero.

Reference solution

Python

from typing import List

def shortestDistance(wordsDict: List[str], word1: str, word2: str) -> int:
    i1 = i2 = -1
    best = -1
    for i, w in enumerate(wordsDict):
        if w == word1:
            i1 = i
        if w == word2:
            i2 = i
        if i1 >= 0 and i2 >= 0:
            d = abs(i1 - i2)
            if best < 0 or d < best:
                best = d
    return best

JavaScript

var shortestDistance = function(wordsDict, word1, word2) {
    var i1 = -1, i2 = -1, best = -1;
    for (var i = 0; i < wordsDict.length; i++) {
        if (wordsDict[i] === word1) i1 = i;
        if (wordsDict[i] === word2) i2 = i;
        if (i1 >= 0 && i2 >= 0) {
            var d = Math.abs(i1 - i2);
            if (best < 0 || d < best) best = d;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy