Shortest Word Distance

Easy Arrays & Hashing Two Pointer Original on LeetCode

Shortest Word Distance is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (one pass with last-seen indices), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (compare every pair of occurrences) up.

Problem

You are given an array of strings wordsDict and two different strings word1 and word2 that both occur in it (possibly several times).

Return the smallest distance between an occurrence of word1 and an occurrence of word2, where the distance between positions i and j is |i - j|.

Examples

Example 1

Input
wordsDict = ["plan", "code", "test", "ship", "code", "rest"], word1 = "plan", word2 = "ship"
Output
3
Why
"plan" is at index 0 and "ship" at index 3, so they are 3 apart.

Example 2

Input
wordsDict = ["cat", "dog", "bird", "cat", "fish", "dog"], word1 = "dog", word2 = "cat"
Output
1
Why
The "dog" at index 1 sits right after the "cat" at index 0.

Constraints

  • 2 <= wordsDict.length <= 3 * 10^4
  • 1 <= wordsDict[i].length <= 10, lowercase English letters.
  • word1 and word2 both appear in wordsDict, and word1 != word2.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (compare every pair of occurrences)O(n²)O(1)
Optimal (one pass with last-seen indices)O(n)O(1)

1Brute force (compare every pair of occurrences)

TimeO(n²)For each of up to n positions the whole list is scanned again.
SpaceO(1)Only a few integers.

For every index holding word1, look at every index holding word2 and keep the smallest absolute difference.

  1. best = infinity.
  2. For each i where wordsDict[i] equals word1:
  3. For each j where wordsDict[j] equals word2, best = min(best, |i - j|).
  4. Return best.
class Solution {
    public int shortestDistance(String[] wordsDict, String word1, String word2) {
        int n = wordsDict.length;
        int best = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (!wordsDict[i].equals(word1)) continue;
            for (int j = 0; j < n; j++) {
                if (wordsDict[j].equals(word2)) {
                    best = Math.min(best, Math.abs(i - j));
                }
            }
        }
        return best;
    }
}

2Optimal (one pass with last-seen indices)

TimeO(n)One pass; each step does at most two string comparisons of length up to 10.
SpaceO(1)Two indices and the answer.

Scan once and remember the latest index of word1 (i1) and of word2 (i2). Whenever one of them moves and both have been seen, |i1 - i2| is a candidate. An older occurrence of the other word is always farther away than its latest one, so no pair that could win is skipped.

  1. i1 = i2 = -1, best = infinity.
  2. For each index k: if wordsDict[k] equals word1, i1 = k; else if it equals word2, i2 = k.
  3. If both i1 and i2 are set, best = min(best, |i1 - i2|).
  4. Return best.
class Solution {
    public int shortestDistance(String[] wordsDict, String word1, String word2) {
        int i1 = -1, i2 = -1;
        int best = Integer.MAX_VALUE;
        for (int k = 0; k < wordsDict.length; k++) {
            if (wordsDict[k].equals(word1)) i1 = k;
            else if (wordsDict[k].equals(word2)) i2 = k;
            if (i1 != -1 && i2 != -1) best = Math.min(best, Math.abs(i1 - i2));
        }
        return best;
    }
}

Edge cases to test

  • The two words are next to each other: the answer is 1
  • Each word appears exactly once, at the two ends of the list
  • Many copies of both words, where the closest pair is not the first occurrences
  • word2 appears before word1 in the list

Hints

Hint 1

Comparing every occurrence of word1 with every occurrence of word2 works, but is quadratic in the worst case.

Hint 2

Walking left to right, the best partner for the current word is the most recent occurrence of the other word. Why can an older one never be closer?

Hint 3

Keep the last index of each word and update the answer whenever either one changes.

FAQ

What is the best time complexity for Shortest Word Distance?

Optimal (one pass with last-seen indices) runs in O(n) time and O(1) extra space. One pass; each step does at most two string comparisons of length up to 10.

Which pattern does Shortest Word Distance use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Shortest Word Distance?

Yes. Brute force (compare every pair of occurrences) takes O(n²) time and O(1) space. For every index holding word1, look at every index holding word2 and keep the smallest absolute difference.

Which edge cases should I test for Shortest Word Distance?

The two words are next to each other: the answer is 1; Each word appears exactly once, at the two ends of the list; Many copies of both words, where the closest pair is not the first occurrences; word2 appears before word1 in the list.