Shortest Word Distance II

Shortest Word Distance II

What is this problem about?

The Shortest Word Distance II interview question extends Shortest Word Distance I by requiring a class design that preprocesses the word array once, then answers multiple shortest(word1, word2) queries efficiently. Each query asks for the minimum distance between any occurrence of word1 and any occurrence of word2. Preprocessing the positions of each word enables O(m + n) per query instead of O(array_length) per query.

Why is this asked in interviews?

LinkedIn, Anduril, and Google ask this design problem because it tests the tradeoff between preprocessing and query time — a fundamental systems design consideration. Storing sorted position lists per word allows using a two-pointer merge to find the minimum distance between two position lists in O(m + n) per query. It models search engine "nearest occurrence" queries that are called millions of times on preprocessed indices.

Algorithmic pattern used

The pattern is hash map of positions + two-pointer merge. In __init__, build a dictionary {word: [sorted list of indices]}. In shortest(word1, word2), retrieve both position lists. Use two pointers i=0, j=0 on the two lists. Compute abs(list1[i] - list2[j]) as the current distance. Advance the pointer with the smaller index value (to potentially find a closer pair). Track the minimum distance. This is O(m + n) per query where m and n are occurrence counts.

Example explanation

words = ["practice","makes","perfect","coding","makes"].

Positions: {"practice":[0], "makes":[1,4], "perfect":[2], "coding":[3]}.

Query shortest("makes", "coding"):

• lists: [1,4] and [3].
• i=0,j=0: |1-3|=2. 1<3 → i++.
• i=1,j=0: |4-3|=1. min=1. 3<4 → j++ → j out of bounds.

Answer: 1.

Common mistakes candidates make

• Reprocessing the word array on each query — the entire point of the class design is to preprocess once.
• Using nested loops O(m×n) to compare all pairs instead of two-pointer O(m+n).
• Not advancing the smaller-index pointer — the two-pointer technique requires advancing the pointer whose current value is smaller to potentially find a closer match.
• Not handling the case where word1 or word2 appears only once — still works with the two-pointer, but edge cases around empty lists should be guarded.

Interview preparation tip

For the Shortest Word Distance II coding problem, the hash table two-pointer design string interview pattern is the key. The two-pointer merge on sorted position lists is an important pattern — it finds the minimum absolute difference between two sorted arrays in O(m+n), much better than the O(mn) brute force. LinkedIn and Google interviewers specifically test this optimization. Practice the two-pointer pattern: always advance the pointer pointing to the smaller value, and update the minimum at each step. This approach generalizes to merging sorted streams and finding minimum gaps between two sorted sequences.