243. Shortest Word Distance - Detailed Explanation

Problem Statement

You’re given an array of strings words and two distinct strings word1 and word2 that both appear in words. Return the shortest distance (in indices) between any occurrence of word1 and any occurrence of word2. Formally, find the minimum value of |i – j| such that words[i] == word1 and words[j] == word2.

Examples

Example 1

Input  
 words = ["practice","makes","perfect","coding","makes"]  
 word1 = "coding", word2 = "practice"  
Output  
 3  
Explanation  
 "coding" is at index 3 and "practice" at index 0 → |3 − 0| = 3

Example 2

Input  
 words = ["practice","makes","perfect","coding","makes"]  
 word1 = "makes", word2 = "coding"  
Output  
 1  
Explanation  
 Closest "makes" at index 4 and "coding" at index 3 → |4 − 3| = 1

Constraints

2 ≤ words.length ≤ 3·10⁴
1 ≤ words[i].length ≤ 10
word1 != word2
Both word1 and word2 are guaranteed to appear in words.

Hints

Brute force checking every pair of positions is O(n²) and too slow for large n.
You only need to remember the last seen index of each target word as you scan.
Update the minimum distance whenever you encounter either target and you have seen the other at least once.

Approach

One‑Pass with Two Pointers

Initialize idx1 = -1, idx2 = -1, and minDist = +∞.
Loop i from 0 to words.length-1:
- If words[i] == word1, set idx1 = i.
- Else if words[i] == word2, set idx2 = i.
- If both idx1 and idx2 are ≥ 0, update
```
minDist = min(minDist, |idx1 - idx2|)
```
Return minDist at the end.

This keeps it O(n) time and O(1) extra space.

Step‑by‑Step (Example 2)

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

i=0: "practice" → no change
i=1: "makes"   → idx1=1, idx2=-1 → can't update yet
i=2: "perfect" → no change
i=3: "coding"  → idx2=3, idx1=1 → minDist = |3-1|=2
i=4: "makes"   → idx1=4, idx2=3 → minDist = min(2,|4-3|=1) = 1
Return 1

Complexity Analysis

Time: O(n), a single pass through words.
Space: O(1), only a few integer variables.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Common Mistakes

Forgetting to check distance right after updating an index.
Using two separate loops instead of a single scan (still correct but less concise).
Initializing minDist to 0 instead of a large value, causing incorrect early minima.

Edge Cases

The first occurrence of one word appears at index 0 and the other at the very end.
Multiple interleaved occurrences—ensure you always compare to the most recent other index.