Skip to main content
Talentd

Shortest Word Distance III - Solution & Explanation

MediumPremiumFree on FleetCodeArrayString8 min readAsked at: Palantir, LinkedIn
Practice this problem

Problem Statement

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 <= 105
  • 1 <= wordsDict[i].length <= 10
  • wordsDict[i] consists of lowercase English letters.
  • word1 and word2 are in wordsDict.

Approach Overview

Problem Overview: You are given an array of words and two target strings word1 and word2. The task is to compute the smallest index distance between occurrences of these words in the list. The twist: word1 and word2 can be the same, which changes how distances must be calculated.

Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)

Scan the array and record every index where word1 and word2 appear. Then compare every valid pair and compute the absolute index difference. If the words are different, compare indices from both sets. If the words are the same, compare consecutive occurrences to avoid zero distance from the same index. This method is straightforward but inefficient because it checks many unnecessary pairs, making it quadratic in the worst case.

Approach 2: Single Pass Case Analysis (O(n) time, O(1) space)

Traverse the array once while tracking the most recent positions of the target words. Maintain two variables such as idx1 and idx2. When you encounter word1, update idx1; when you encounter word2, update idx2. After each update, compute abs(idx1 - idx2) and update the minimum distance.

The key insight appears when word1 == word2. Instead of keeping two independent indices, treat the current occurrence as the next candidate and compute the distance from the previous occurrence of the same word. Practically, you store the previous index and update the minimum whenever the word appears again. This prevents comparing the same index with itself while still capturing the closest pair.

This approach works because the closest distance must occur between two nearby occurrences in the traversal order. By updating indices during iteration, you avoid storing extra data structures and achieve linear time.

Problems like this frequently appear in interviews that test efficient scanning and state tracking over arrays. The technique is closely related to patterns used in array traversal and string processing problems, where maintaining the last seen index enables constant-time updates.

Recommended for interviews: The single-pass case analysis solution is the expected answer. It demonstrates you can reason about edge cases like identical words while maintaining O(n) efficiency. Mentioning the brute force approach first shows baseline understanding, but implementing the linear scan with correct handling for word1 == word2 shows strong problem-solving ability.

Solution

First, we check whether word1 and word2 are equal:

  • If they are equal, iterate through the array wordsDict to find two indices i and j of word1, and compute the minimum value of i-j.
  • If they are not equal, iterate through the array wordsDict to find the indices i of word1 and j of word2, and compute the minimum value of i-j.

The time complexity is O(n), where n is the length of the array wordsDict. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ComparisonO(n²)O(1)Useful for understanding the problem or when the array size is extremely small.
Index List + Pair ScanO(n + k²)O(k)When you want clearer separation of word positions before computing distances.
Single Pass Case AnalysisO(n)O(1)Best general solution for interviews and large inputs.

Video Solution

Shortest Word Distance III - Python - LeetCode 245 • Code with Carter • 1,147 views views

Watch 4 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Shortest Word Distance III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Shortest Word Distance

Next

Shortest Word Distance II