Watch 10 video solutions for Shortest Word Distance, a easy level problem involving Array, String. This walkthrough by hakunamatasq has 3,652 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of strings wordsDict and two different strings that already exist in the array word1 and word2, return the shortest distance between these two words in the list.
Example 1:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice" Output: 3
Example 2:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding" Output: 1
Constraints:
2 <= wordsDict.length <= 3 * 1041 <= wordsDict[i].length <= 10wordsDict[i] consists of lowercase English letters.word1 and word2 are in wordsDict.word1 != word2Problem Overview: You receive an array of words and two target words. The task is to return the minimum index distance between any occurrence of word1 and word2 in the list. Distance is defined as the absolute difference between their indices.
Approach 1: Brute Force Pair Comparison (O(n^2) time, O(1) space)
The most direct approach checks every possible pair of indices where the words match word1 and word2. First iterate through the array and record positions of each target word, or simply compare during nested iteration. For each match of word1, scan the rest of the array to find occurrences of word2 and compute abs(i - j). Track the minimum distance seen. This approach works but performs redundant comparisons, especially when the array is large.
Approach 2: Single Pass Index Tracking (O(n) time, O(1) space)
A more efficient strategy scans the array once while keeping track of the most recent index where each target word appeared. Maintain two variables, lastWord1 and lastWord2. As you iterate through the list, update the corresponding index when you encounter either word. Whenever both indices are known, compute the distance abs(lastWord1 - lastWord2) and update the minimum result.
The key insight is that the closest pair must involve the latest occurrence of one word relative to the other. There is no need to store all positions or perform nested scans. Each element is processed once, making the algorithm linear and memory efficient.
This technique is common in array traversal problems and works well when scanning ordered data where relative positions matter. Since the input consists of words, the logic also fits naturally into string processing tasks where you track occurrences during iteration.
Recommended for interviews: The single-pass index tracking approach is what interviewers expect. Mentioning the brute force solution shows you understand the baseline, but moving to the O(n) scan demonstrates optimization skills and familiarity with efficient array traversal patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n^2) | O(1) | Useful for understanding the problem or when constraints are very small |
| Single Pass Index Tracking | O(n) | O(1) | Best general solution for large arrays and interview scenarios |