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

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

Approach

One‑Pass with Two Pointers

1. Initialize idx1 = -1, idx2 = -1, and minDist = +∞.
2. 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|)
     

3. 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