Shortest Word Distance II - Practice Coding Problems

Shortest Word Distance II - Problem

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

WordDistance(String[] wordsDict) - initializes the object with the strings array wordsDict
int shortest(String word1, String word2) - returns the shortest distance between word1 and word2 in the array wordsDict

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

Input & Output

Example 1 — Basic Operations

$ Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], operations = [["shortest", "coding", "practice"], ["shortest", "makes", "coding"]]

› Output: [3, 1]

💡 Note: First query: "coding" is at index 3, "practice" at index 0, distance = |3-0| = 3. Second query: "makes" at indices [1,4], "coding" at index 3, minimum distance = min(|1-3|, |4-3|) = min(2,1) = 1.

Example 2 — Same Word Multiple Positions

$ Input: wordsDict = ["a", "b", "a", "b"], operations = [["shortest", "a", "b"]]

› Output: [1]

💡 Note: "a" appears at indices [0,2], "b" appears at indices [1,3]. Possible distances: |0-1|=1, |0-3|=3, |2-1|=1, |2-3|=1. Minimum is 1.

Example 3 — Adjacent Words

$ Input: wordsDict = ["hello", "world", "coding"], operations = [["shortest", "hello", "world"]]

› Output: [1]

💡 Note: "hello" at index 0, "world" at index 1. Distance = |0-1| = 1 (adjacent positions).

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 with repeated entries

Process

Build index mapping and answer distance queries

Output

Minimum distance for each query

Key Takeaway

🎯 Key Insight: Preprocess once to build word-to-positions mapping, then use two pointers for efficient minimum distance queries

Asked in

G Google 25 in LinkedIn 15 f Facebook 12 a Amazon 8

The optimal approach uses hash map preprocessing to store each word's positions, then applies two-pointer technique to find minimum distance between position lists. Best approach: Hash Map + Two Pointers - Time: O(m+n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Preprocessing	O(m + n)	O(n)	Preprocess array to map each word to all its positions for O(1) lookup
Brute Force - Linear Search Every Time	O(n)	O(n)	Scan the entire array for each query to find all positions

Hash Map Preprocessing — Algorithm Steps

Step 1: Create hash map during initialization
Step 2: For each word, store all indices where it appears
Step 3: For queries, get position lists from hash map in O(1)
Step 4: Use two pointers to find minimum distance between sorted lists

Visualization

Tap to expand

Step-by-Step Walkthrough

Preprocess

Build hash map: word → list of all indices

Query

Get position lists for both words in O(1)

Two Pointers

Find minimum distance using two pointers on sorted lists

Code -

solution.c — C

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

#define MAX_WORDS 1000
#define MAX_WORD_LEN 100
#define MAX_INDICES 1000

typedef struct {
    char word[MAX_WORD_LEN];
    int indices[MAX_INDICES];
    int count;
} WordEntry;

typedef struct {
    WordEntry entries[MAX_WORDS];
    int size;
} WordDistance;

WordDistance* wordDistanceCreate(char** wordsDict, int wordsDictSize) {
    WordDistance* obj = (WordDistance*)malloc(sizeof(WordDistance));
    obj->size = 0;
    
    for (int i = 0; i < wordsDictSize; i++) {
        // Find existing word or create new entry
        int found = -1;
        for (int j = 0; j < obj->size; j++) {
            if (strcmp(obj->entries[j].word, wordsDict[i]) == 0) {
                found = j;
                break;
            }
        }
        
        if (found != -1) {
            obj->entries[found].indices[obj->entries[found].count++] = i;
        } else {
            strcpy(obj->entries[obj->size].word, wordsDict[i]);
            obj->entries[obj->size].indices[0] = i;
            obj->entries[obj->size].count = 1;
            obj->size++;
        }
    }
    
    return obj;
}

int wordDistanceShortest(WordDistance* obj, char* word1, char* word2) {
    WordEntry* entry1 = NULL;
    WordEntry* entry2 = NULL;
    
    // Find entries for both words
    for (int i = 0; i < obj->size; i++) {
        if (strcmp(obj->entries[i].word, word1) == 0) {
            entry1 = &obj->entries[i];
        }
        if (strcmp(obj->entries[i].word, word2) == 0) {
            entry2 = &obj->entries[i];
        }
    }
    
    // Two pointer approach
    int i = 0, j = 0;
    int minDist = INT_MAX;
    
    while (i < entry1->count && j < entry2->count) {
        int dist = abs(entry1->indices[i] - entry2->indices[j]);
        if (dist < minDist) {
            minDist = dist;
        }
        
        if (entry1->indices[i] < entry2->indices[j]) {
            i++;
        } else {
            j++;
        }
    }
    
    return minDist;
}

int* solution(char** wordsDict, int wordsDictSize, char*** operations, int operationsSize, int* returnSize) {
    WordDistance* wd = wordDistanceCreate(wordsDict, wordsDictSize);
    int* results = (int*)malloc(operationsSize * sizeof(int));
    int resultCount = 0;
    
    for (int i = 0; i < operationsSize; i++) {
        if (strcmp(operations[i][0], "shortest") == 0) {
            results[resultCount++] = wordDistanceShortest(wd, operations[i][1], operations[i][2]);
        }
    }
    
    *returnSize = resultCount;
    return results;
}

int main() {
    // Simplified implementation for this example
    char* wordsDict[] = {"practice", "makes", "perfect", "coding", "makes"};
    char** ops1[] = {{"shortest", "coding", "practice"}, {"shortest", "makes", "coding"}};
    int returnSize;
    
    int* result = solution(wordsDict, 5, (char***)ops1, 2, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m + n)

O(n) preprocessing + O(m) per query where m is sum of word occurrences

✓ Linear Growth

Space Complexity

O(n)

Hash map stores all n indices distributed across word lists

⚡ Linearithmic Space

28.0K 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

Hash Map Preprocessing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler