Is Shortest Word Distance easy or hard?

Shortest Word Distance is classified as an Easy problem. The brute force idea is straightforward, and the optimal O(n) solution relies on simple index tracking during a single pass through the array.

Shortest Word Distance Python/Java solution

In Python or Java, the solution iterates through the words array and updates two variables representing the last seen positions of the target words. Each update checks the absolute difference between indices to maintain the minimum distance. The logic is identical across Python, Java, C++, and Go.

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

Iterate through the words array while storing the most recent indices of word1 and word2. When either word appears, update its index and compute the distance with the other stored index if available. Keep the minimum distance during the scan.

What is the best approach for Shortest Word Distance?

The best approach is a single-pass scan that tracks the last seen index of each target word. Each time one of the words appears, update its index and compute the absolute difference with the other word's last position. This runs in O(n) time and O(1) space.

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

Shortest Word Distance and its variations frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests array traversal, index tracking, and the ability to optimize from a brute force solution to a linear-time approach.

What data structure is used in Shortest Word Distance?

The optimal solution only uses simple variables to store indices, making it primarily an array traversal problem. Some variations may store indices in lists or hash maps, but the standard solution needs constant extra space.

What is the time complexity of Shortest Word Distance?

The optimal solution runs in O(n) time because the array is traversed exactly once. Space complexity is O(1) since only two index variables are maintained to track the latest positions of the target words.

Description Solution Video 5:22

243. Shortest Word Distance

Easy66.3% acceptance8 companiesPremium elsewhere, free here

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

Example 1:

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

Example 2:

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

Constraints:

2 <= wordsDict.length <= 3 * 10⁴
1 <= wordsDict[i].length <= 10
wordsDict[i] consists of lowercase English letters.
word1 and word2 are in wordsDict.
word1 != word2

Asked at 8 companies

Snowflake Wix Anduril Patreon LinkedIn Apple Amazon Microsoft

Topics

Array String

5:22

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

Open solution

243. Shortest Word Distance

Asked at 8 companies

Topics

Similar problems