Shortest Word Distance

Shortest Word Distance

What is this problem about?

The Shortest Word Distance interview question gives you an array of strings and two target words word1 and word2. Find the minimum distance (difference in indices) between any occurrence of word1 and any occurrence of word2 in the array. This is a simple linear scan problem — find the nearest pair of occurrences across both words.

Why is this asked in interviews?

Apple, Microsoft, Amazon, LinkedIn, and Anduril ask this problem because it tests the classic "track the last seen position of each element" pattern. It validates that candidates can maintain running positions and compute pairwise distances in a single pass, rather than naively finding all positions and comparing all pairs in O(n^2). This directly models "nearest neighbor" queries in recommendation systems and text search engines.

Algorithmic pattern used

The pattern is single-pass scan with position tracking. Scan the array while tracking the most recently seen index of word1 (idx1) and word2 (idx2). When word1 is found, update idx1 and compute |idx1 - idx2| if idx2 is valid. When word2 is found, update idx2 and compute |idx1 - idx2| if idx1 is valid. Track the running minimum distance. This is O(n) time and O(1) space.

Example explanation

words = ["hello","world","hello","go","world"], word1 = "hello", word2 = "world".

Scan:

• Index 0 ("hello"): idx1=0. idx2 invalid.
• Index 1 ("world"): idx2=1. |0-1|=1. min=1.
• Index 2 ("hello"): idx1=2. |2-1|=1. min=1.
• Index 3 ("go"): skip.
• Index 4 ("world"): idx2=4. |2-4|=2. min still 1.

Answer: 1.

Common mistakes candidates make

• Storing all positions of both words and doing pairwise comparisons — O(n^2) when O(n) is possible.
• Not initializing idx1 and idx2 to -1 or infinity — attempting to compute distance before both have been seen causes incorrect results.
• Not updating the index BEFORE computing the distance — update idx first, then compute the new distance with the just-updated value.
• Using abs(idx1 - idx2) but forgetting to check both are valid (non-negative) before computing.

Interview preparation tip

For the Shortest Word Distance coding problem, the array string two-pointer interview pattern is the simple O(n) approach. The single-scan solution is the ideal answer — maintain two most-recent indices and update the minimum on each word encounter. LinkedIn interviewers ask this as a warmup before the harder variants (Shortest Word Distance II with repeated queries, Shortest Word Distance III where word1 and word2 can be the same). Know that solving this cleanly in O(n) prepares you for all three variants — the position-tracking pattern is the common thread across all of them.