Shortest Word Distance

Easy
765.

Shortest Word Distance

Shortest Word Distance is an easy coding problem on arrays, strings and two pointers, asked in Amazon, Meta and Infosys interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} wordsDict
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var shortestDistance = function(wordsDict, word1, word2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Shortest Word Distance — Solution in Python, Java & C++

Shortest Word Distance solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Shortest Word Distance is an easy coding problem on arrays, strings and two pointers, asked in Amazon, Meta and Infosys interviews.

  • Difficulty: Easy
  • Topics: Arrays, Strings, Two Pointers
  • Asked at: Amazon, Meta, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Shortest Word Distance

  1. Hint 1

    One pass is enough: remember the most recent index of each word.

  2. Hint 2

    Whenever both have been seen, their current indices give a candidate distance.

  3. Hint 3

    The most recent occurrence is always the best partner for the word just encountered.

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

Java

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

C++

int shortestDistance(vector<string>& wordsDict, string word1, string word2) {
    int i1 = -1, i2 = -1, best = -1;
    for (int i = 0; i < (int) wordsDict.size(); i++) {
        if (wordsDict[i] == word1) i1 = i;
        if (wordsDict[i] == word2) i2 = i;
        if (i1 >= 0 && i2 >= 0) {
            int d = abs(i1 - i2);
            if (best < 0 || 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings