Shortest Word Distance - Solution & Explanation

Problem Overview: Given a list of words and two target words, return the minimum distance between their indices in the array. Distance is defined as the absolute difference between positions where the two words appear.

Approach 1: Brute Force Comparison (O(n²) time, O(1) space)

Iterate through the array and collect every index where word1 and word2 appear. Then compare every pair of indices and compute the absolute difference. Track the minimum value across all comparisons. This works because every possible occurrence pair is evaluated, but the nested comparisons make it inefficient for large arrays.

This approach is mainly useful for understanding the problem mechanics. You explicitly check all valid distances but pay a quadratic cost.

Approach 2: Two Lists + Two Pointers (O(n) time, O(n) space)

First scan the array once and store all indices of word1 and word2 in two separate lists. Since indices are naturally collected in sorted order, you can apply a two-pointer technique similar to merging sorted arrays. Move the pointer pointing to the smaller index and update the minimum distance at each step.

This reduces comparisons significantly compared to brute force. It still uses extra memory to store index lists but runs in linear time overall.

Approach 3: Single Pass Index Tracking (O(n) time, O(1) space)

Traverse the array once while tracking the latest seen index of word1 and word2. Each time you encounter either word, update its index. If both indices have been seen, compute abs(index1 - index2) and update the minimum distance.

The key insight: only the most recent occurrences matter for minimizing distance during a sequential scan. Earlier occurrences would always produce a larger gap than the most recent one. This makes it possible to solve the problem in a single pass with constant memory.

This pattern appears frequently in array traversal problems and interview questions involving string comparisons or streaming updates.

Recommended for interviews: The single-pass index tracking approach is what interviewers expect. It demonstrates strong understanding of state tracking during iteration and achieves the optimal O(n) time and O(1) space. Starting with the brute force idea shows you understand the problem, then refining it to the one-pass solution shows algorithmic optimization skills.