Skip to main content
Talentd

Shortest Word Distance - Solution & Explanation

EasyPremiumFree on FleetCodeArrayString4 min readAsked at: Amazon, Microsoft, Apple +5
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive an array of words and two target words. The task is to return the minimum index distance between any occurrence of word1 and word2 in the list. Distance is defined as the absolute difference between their indices.

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

The most direct approach checks every possible pair of indices where the words match word1 and word2. First iterate through the array and record positions of each target word, or simply compare during nested iteration. For each match of word1, scan the rest of the array to find occurrences of word2 and compute abs(i - j). Track the minimum distance seen. This approach works but performs redundant comparisons, especially when the array is large.

Approach 2: Single Pass Index Tracking (O(n) time, O(1) space)

A more efficient strategy scans the array once while keeping track of the most recent index where each target word appeared. Maintain two variables, lastWord1 and lastWord2. As you iterate through the list, update the corresponding index when you encounter either word. Whenever both indices are known, compute the distance abs(lastWord1 - lastWord2) and update the minimum result.

The key insight is that the closest pair must involve the latest occurrence of one word relative to the other. There is no need to store all positions or perform nested scans. Each element is processed once, making the algorithm linear and memory efficient.

This technique is common in array traversal problems and works well when scanning ordered data where relative positions matter. Since the input consists of words, the logic also fits naturally into string processing tasks where you track occurrences during iteration.

Recommended for interviews: The single-pass index tracking approach is what interviewers expect. Mentioning the brute force solution shows you understand the baseline, but moving to the O(n) scan demonstrates optimization skills and familiarity with efficient array traversal patterns.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ComparisonO(n^2)O(1)Useful for understanding the problem or when constraints are very small
Single Pass Index TrackingO(n)O(1)Best general solution for large arrays and interview scenarios

Video Solution

243. Shortest Word Distance (LeetCode) • hakunamatasq • 4,044 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Find All K-Distant Indices in an Array

Next

Shortest Word Distance II