Is Shortest Word Distance III easy or hard?

Shortest Word Distance III is generally classified as a medium difficulty problem. The challenge comes from handling the case where both target words are the same while still computing the correct minimum distance in a single pass.

Shortest Word Distance III Python/Java solution

Most implementations follow the same logic across languages: iterate once, update the latest indices for the target words, and maintain the minimum distance. The algorithm translates directly into Python, Java, C++, Go, or TypeScript with identical O(n) time complexity.

How to solve Shortest Word Distance III in O(n)?

Iterate through the word list while keeping track of the last index where each target word appeared. When you encounter either word, update its index and compute the distance to the other index. If both target words are identical, track the previous occurrence and compute the distance between consecutive appearances. This maintains a running minimum in linear time.

What is the best approach for Shortest Word Distance III?

The best approach is a single-pass scan that tracks the most recent indices of the target words. Update the index whenever a word appears and compute the absolute difference between indices. A small modification handles the case when both target words are the same. This solution runs in O(n) time and O(1) space.

Is Shortest Word Distance III asked at Google/Amazon/Meta?

Variants of the Shortest Word Distance problems have appeared in interviews at companies like Google, Amazon, and Meta. They test efficient array traversal, handling edge cases, and reasoning about index distances. Interviewers expect the O(n) single-pass solution.

What data structure is used in Shortest Word Distance III?

The optimal solution mainly uses simple integer variables to track the last seen positions of words during array traversal. No complex data structures are required, though the problem conceptually relies on array scanning and index tracking.

What is the time complexity of Shortest Word Distance III?

The optimal solution runs in O(n) time where n is the number of words in the array. Each element is visited exactly once while maintaining the last seen indices. Space complexity is O(1) because only a few integer variables are stored.

Description Solution Video 10:20

245. Shortest Word Distance III

Medium59.4% acceptance2 companiesPremium elsewhere, free here

Given an array of strings wordsDict and two strings that already exist in the array word1 and word2, return the shortest distance between the occurrence of these two words in the list.

Note that word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list.

Example 1:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

Example 2:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
Output: 3

Constraints:

1 <= wordsDict.length <= 10⁵
1 <= wordsDict[i].length <= 10
wordsDict[i] consists of lowercase English letters.
word1 and word2 are in wordsDict.

Asked at 2 companies

Palantir LinkedIn

Topics

Array String

10:20

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

245. Shortest Word Distance III

Asked at 2 companies

Topics

Similar problems