Shortest Word Distance II - Video Solutions

Problem Overview: You receive a list of words during initialization and must design a class that repeatedly answers queries asking for the shortest index distance between two given words. Each query should be efficient because the same word list is reused many times.

Approach 1: Scan the Array for Every Query (O(n) time, O(1) space)

The most direct approach is to scan the entire array whenever shortest(word1, word2) is called. Track the most recent index of each target word while iterating through the list and update the minimum distance whenever both have appeared. This works because the closest pair will appear during the scan. However, if the function is called many times, repeatedly scanning the same array becomes expensive. Time complexity is O(n) per query and space complexity is O(1).

Approach 2: Hash Map of Word Indices + Two Pointers (O(k) query, O(n) preprocessing)

Preprocess the word list once and store the indices of each word in a HashMap where the key is the word and the value is a sorted list of positions. For a query, retrieve the two index lists and use the two pointers technique to find the smallest difference between elements in the two sorted lists. Move the pointer pointing to the smaller index because that is the only way to potentially reduce the distance. Preprocessing costs O(n) time and space. Each query runs in O(k), where k is the combined size of the two index lists.

This approach works well because indices for each word are naturally sorted as you iterate through the original array. The pointer comparison avoids checking every pair of positions and instead progresses linearly through both lists. The idea combines hash table lookup for fast access and two pointers for efficient distance calculation.

Approach 3: Hash Map + Binary Search (O(log m) per comparison)

Another option stores the same index lists but uses binary search for each index in the first list to find the closest position in the second list. Because each list is sorted, binary search can quickly locate the nearest neighbor. This gives roughly O(m log n) per query depending on the list sizes. While slightly slower in practice than the two-pointer sweep, it can be useful if one list is significantly smaller than the other. The preprocessing step still requires O(n) time and space using a array traversal.

Recommended for interviews: The hash map with two pointers approach is what interviewers typically expect. It shows you recognize the repeated-query pattern and move work into preprocessing. Mentioning the brute-force scan first demonstrates baseline reasoning, but implementing the indexed map with two pointers shows stronger algorithmic design.