Shortest Word Distance - Practice Coding Problems

Shortest Word Distance - Problem

Array String Easy

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

The distance between two words is the absolute difference of their indices in the array.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: word1 "coding" is at index 3, word2 "practice" is at index 0. Distance = |3-0| = 3

Example 2 — Multiple Occurrences

$ Input: wordsDict = ["practice", "makes", "perfect", "practice", "makes", "perfect"], word1 = "practice", word2 = "perfect"

› Output: 1

💡 Note: "practice" appears at indices 0,3 and "perfect" at indices 2,5. Minimum distance is between indices 3 and 2: |3-2| = 1

Example 3 — Adjacent Words

$ Input: wordsDict = ["a", "b", "c"], word1 = "a", word2 = "b"

› Output: 1

💡 Note: "a" is at index 0, "b" is at index 1. Distance = |0-1| = 1

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words and two target words to find

Process

Find all positions and calculate minimum distance

Output

Return the shortest distance found

Key Takeaway

🎯 Key Insight: Track the most recent positions of target words to find minimum distance in one pass

Asked in

Li LinkedIn 15 f Facebook 12 G Google 8 M Microsoft 6

The key insight is that we only need to track the most recent positions of both target words. The optimal approach scans the array once, updating positions and calculating distances in real-time. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n²)	O(n)	Find all occurrences of both words and check every possible pair
One Pass - Track Latest Positions	O(n)	O(1)	Track most recent positions of both words while scanning once

Brute Force - Check All Pairs — Algorithm Steps

Find all indices where word1 appears
Find all indices where word2 appears
Calculate distance between every pair of indices
Return the minimum distance found

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Positions

Locate all indices of both words

Check Pairs

Calculate distance between every pair

Return Minimum

Keep track of smallest distance found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(char wordsDict[][100], int dictSize, char* word1, char* word2) {
    int indices1[1000], indices2[1000];
    int count1 = 0, count2 = 0;
    
    // Find all indices of word1 and word2
    for (int i = 0; i < dictSize; i++) {
        if (strcmp(wordsDict[i], word1) == 0) {
            indices1[count1++] = i;
        } else if (strcmp(wordsDict[i], word2) == 0) {
            indices2[count2++] = i;
        }
    }
    
    // Find minimum distance between any pair
    int minDist = INT_MAX;
    for (int i = 0; i < count1; i++) {
        for (int j = 0; j < count2; j++) {
            int dist = abs(indices1[i] - indices2[j]);
            if (dist < minDist) {
                minDist = dist;
            }
        }
    }
    
    return minDist;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    char wordsDict[1000][100];
    int dictSize = 0;
    char* token = strtok(line, "[],\"");
    while (token != NULL) {
        while (*token == ' ') token++;
        if (strlen(token) > 0) {
            strcpy(wordsDict[dictSize++], token);
        }
        token = strtok(NULL, "[],\"");
    }
    
    char word1[100], word2[100];
    fgets(word1, sizeof(word1), stdin);
    fgets(word2, sizeof(word2), stdin);
    word1[strcspn(word1, "\n")] = 0;
    word2[strcspn(word2, "\n")] = 0;
    
    int result = solution(wordsDict, dictSize, word1, word2);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case, if most elements are word1 or word2, we check every pair of positions

⚠ Quadratic Growth

Space Complexity

O(n)

Store all positions of word1 and word2 in separate arrays

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler