245. Shortest Word Distance III

MediumArrayString
Leetcode Link

Problem Description

The problem presents us with an array of strings called wordsDict, where we must find the minimum distance between two specified words, word1 and word2. This distance is defined as the number of positions between the two words in the array. An important condition given is that word1 and word2 can sometimes be the same word in the list, although generally, they represent distinct words. The goal is to write a function that returns the smallest number of indices between the two occurrences of these words.

Intuition

The intuitive approach to solving this problem relies on a linear scan through the wordsDict array. We will keep track of the positions where word1 and word2 occur as we iterate through the array. The key is to update the minimum distance whenever we encounter one of the two words.

If word1 and word2 are the same, we need to find the smallest distance between two occurrences of this single word. We can do this by keeping a single pointer (let's call it j) that records the last seen position of the word. As we iterate, each time we encounter the word again, we calculate the distance from the current position to the last seen position and update our answer accordingly.

On the other hand, if word1 and word2 are different, we maintain two separate pointers (say i and j) to track the last seen positions for both words. As we move through the array, if we find either word, we update the respective pointer and check if we've previously seen the other word. If we have, we calculate the distance between the current word's position and the last seen position of the other word and update the minimum distance accordingly.

This solution takes O(n) time since we pass through the array only once, regardless of whether word1 and word2 are the same or different words. It's efficient because it doesn't require extra space for its operations, aside from a few variables.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Solution Approach

The solution implemented here makes use of a few key variables and a single pass through the input list to track the positions of the words and calculate the minimum distance.

Here's a step-by-step breakdown of how the algorithm operates:

  1. Initialization: A variable ans is initialized with the length of wordsDict. This is done because the maximum possible distance between any two words is the length of the array itself. We also initialize two pointers i and j to -1 to represent that we have not yet encountered any of the two words.

  2. Special Case Handling for Identical Words: When word1 and word2 are the same, they will be encountered sequentially at different positions as we iterate. We only need one index j to keep track of the last position where this word was found. Each time we find the word again, we calculate the distance between the current and last positions and update ans if it is smaller than the current ans.

  3. General Case for Different Words: Here, we need to track the most recent positions of word1 and word2 as we iterate. Whenever one of the words is found (w == word1 or w == word2), we update the respective last seen index, i or j. If both i and j have been set (meaning we have found both words at least once), we calculate the absolute difference between their positions to get the current distance. We then update ans if the calculated distance is less than the current ans.

  4. Iteration: The loop goes through every word w in wordsDict with its index k and performs the checks and updates according to the above logic.

  5. Return Statement: After the loop completes, ans contains the smallest distance found between the two words, and this value is returned.

This solution is elegant because it covers both cases (identical and different words) in a single pass and does so with constant space complexity, i.e., the space used does not grow with the input size, and linear time complexity, i.e., it runs in O(n) time, where n is the number of words in wordsDict.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example Walkthrough

Let us consider a small example to illustrate the solution approach. Assume the array wordsDict is ["practice", "makes", "perfect", "coding", "makes"], and we want to find the minimum distance between word1 = "coding" and word2 = "practice".

  1. Initialization:

    • ans is set to the length of wordsDict, which is 5.
    • Two pointers i and j are initialized to -1 as we have not yet found any instance of word1 or word2.

  2. Iteration:

    • We go through each word w in wordsDict along with its index k.
    • At index 0, w = "practice". We recognize this as word1 and update i to 0. Since j is still -1, we do not update ans.
    • At index 1, w = "makes". This does not match word1 or word2, so we continue onwards without updates.
    • At index 3, w = "coding". This is identified as word2, so we update j to 3. Now, we check for i, which is 0. We find the distance between index 3 and index 0 to be 3 and update ans with this value because it's smaller than the current ans.
    • The final word in the array does not match either word1 or word2, so no further actions are taken.

  3. Return Statement:

    • Since we have now finished iterating through wordsDict, the ans variable contains the smallest distance, which is 3. Thus, the function will return 3.

If we alter the conditions slightly and look for the minimum distance between the same word, word1 = "makes" and word2 = "makes", we would only need one pointer as per the special case in our approach.

  1. Initialization:

    • ans set to 5 and j set to -1.

  2. Iteration:

    • At index 1, w = "makes". We update j to 1 (there's nothing to compare with yet, so ans remains unchanged).
    • Continuing through the array, we find "makes" again at index 4. Now, we check the distance from the last position 1 to the current 4, which is 3, and update our answer to 3.

  3. Return Statement:

    • After completing the loop, the final ans is 3, as that is the minimum distance between two instances of "makes".

Solution Implementation

1from typing import List
2
3class Solution:
4    def shortest_word_distance(self, words_dict: List[str], word1: str, word2: str) -> int:
5        # Initialize the minimum distance to the length of the word list
6        min_distance = len(words_dict)
7      
8        # If both words are the same, we need to find the shortest distance
9        # between two occurrences of the same word
10        if word1 == word2:
11            last_occurrence_index = -1  # Initialize the index for the last occurrence of the word
12            for index, word in enumerate(words_dict):
13                if word == word1:
14                    if last_occurrence_index != -1:
15                        # Update minimum distance if the current pair is closer
16                        min_distance = min(min_distance, index - last_occurrence_index)
17                    # Update the last occurrence index to the current index
18                    last_occurrence_index = index
19        else:
20            # If the words are different, find the shortest distance between word1 and word2
21            index1 = index2 = -1  # Initialize the indexes for the occurrences of the words
22          
23            for index, word in enumerate(words_dict):
24                if word == word1:
25                    index1 = index  # Update index when word1 is found
26                if word == word2:
27                    index2 = index  # Update index when word2 is found
28              
29                # If both words have been found, update the minimum distance
30                if index1 != -1 and index2 != -1:
31                    min_distance = min(min_distance, abs(index1 - index2))
32      
33        # Return the minimum distance found
34        return min_distance
35
1class Solution {
2    // Function to find the shortest distance between occurrences of word1 and word2 in wordsDict
3    public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
4        int shortDistance = wordsDict.length; // Initialize to the maximum possible distance
5      
6        // Handle the case where both words are the same
7        if (word1.equals(word2)) {
8            for (int i = 0, prevIndex = -1; i < wordsDict.length; ++i) {
9                if (wordsDict[i].equals(word1)) {
10                    if (prevIndex != -1) {
11                        // Update the shortest distance between two occurrences of word1
12                        shortDistance = Math.min(shortDistance, i - prevIndex);
13                    }
14                    prevIndex = i; // Update prevIndex to the current index
15                }
16            }
17        } else {
18            // When the two words are different
19            for (int k = 0, indexWord1 = -1, indexWord2 = -1; k < wordsDict.length; ++k) {
20                if (wordsDict[k].equals(word1)) {
21                    indexWord1 = k; // Update index for word1
22                }
23                if (wordsDict[k].equals(word2)) {
24                    indexWord2 = k; // Update index for word2
25                }
26                // If both indices are set, calculate distance and update if it's a shorter one
27                if (indexWord1 != -1 && indexWord2 != -1) {
28                    shortDistance = Math.min(shortDistance, Math.abs(indexWord1 - indexWord2));
29                }
30            }
31        }
32        return shortDistance; // Return the shortest distance found
33    }
34}
35
1#include <vector>
2#include <string>
3#include <climits>
4
5using std::vector;
6using std::string;
7using std::min;
8using std::abs;
9
10class Solution {
11public:
12    // Function to find the shortest distance between two words in a dictionary,
13    // where the words could potentially be the same.
14    int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
15        int dictSize = wordsDict.size();  // Get the size of the dictionary.
16        int answer = dictSize;  // Initialize answer with the maximum possible distance.
17      
18        if (word1 == word2) {
19            // Case when both words are the same.
20            for (int i = 0, lastPosition = -1; i < dictSize; ++i) {
21                // Loop through each word in the dictionary.
22                if (wordsDict[i] == word1) {
23                    // When the word matches word1 (which is also word2 in this case).
24                    if (lastPosition != -1) {
25                        // If this is not the first occurrence, calculate the distance
26                        // from the last occurrence.
27                        answer = min(answer, i - lastPosition);
28                    }
29                    // Update last occurrence position.
30                    lastPosition = i;
31                }
32            }
33        } else {
34            // Case when the words are different.
35            for (int k = 0, positionWord1 = -1, positionWord2 = -1; k < dictSize; ++k) {
36                // Loop through each word in the dictionary.
37                if (wordsDict[k] == word1) {
38                    // When the word matches word1, update its last seen position.
39                    positionWord1 = k;
40                } else if (wordsDict[k] == word2) {
41                    // When the word matches word2, update its last seen position.
42                    positionWord2 = k;
43                }
44                // If both words have been seen at least once, calculate the distance.
45                if (positionWord1 != -1 && positionWord2 != -1) {
46                    answer = min(answer, abs(positionWord1 - positionWord2));
47                }
48            }
49        }
50      
51        // Return the shortest distance found.
52        return answer;
53    }
54};
55
1// Import the necessary utilities from Array.prototype
2import { abs, min } from "Math";
3
4// Type definition for a dictionary of words.
5type WordDictionary = string[];
6
7// Function to find the shortest distance between two words in a dictionary,
8// where the words could potentially be the same.
9function shortestWordDistance(wordsDict: WordDictionary, word1: string, word2: string): number {
10    const dictSize: number = wordsDict.length; // Get the size of the dictionary.
11    let answer: number = dictSize; // Initialize answer with the maximum possible distance.
12
13    if (word1 === word2) {
14        // Case when both words are the same.
15        let lastPosition: number = -1; // Initialize the last position.
16        wordsDict.forEach((word, index) => {
17            // Loop through each word in the dictionary.
18            if (word === word1) {
19                // When the word matches word1 (which is also word2 in this case).
20                if (lastPosition !== -1) {
21                    // If this is not the first occurrence, calculate the distance
22                    // from the last occurrence.
23                    answer = min(answer, index - lastPosition);
24                }
25                // Update last occurrence position.
26                lastPosition = index;
27            }
28        });
29    } else {
30        // Case when the words are different.
31        let positionWord1: number = -1; // Initialize position for word1.
32        let positionWord2: number = -1; // Initialize position for word2.
33        wordsDict.forEach((word, index) => {
34            // Loop through each word in the dictionary.
35            if (word === word1) {
36                // When the word matches word1, update its last seen position.
37                positionWord1 = index;
38            } else if (word === word2) {
39                // When the word matches word2, update its last seen position.
40                positionWord2 = index;
41            }
42            // If both words have been seen at least once, calculate the distance.
43            if (positionWord1 !== -1 && positionWord2 !== -1) {
44                answer = min(answer, abs(positionWord1 - positionWord2));
45            }
46        });
47    }
48
49    // Return the shortest distance found.
50    return answer;
51}
52
Not Sure What to Study? Take the 2-min Quiz：

How many ways can you arrange the three letters A, B and C?

Time and Space Complexity

Time Complexity

The given algorithm traverses through the list wordsDict once, regardless of whether word1 and word2 are the same or not.

  • When word1 and word2 are the same, the algorithm iterates over wordsDict, and only performs constant-time operations within the loop (comparison, assignment, arithmetic). Thus, the time complexity is O(n), where n is the length of wordsDict.

  • When word1 and word2 are different, the algorithm again only goes through the list once, doing constant-time operations whenever word1 or word2 is found, and updating indices i and j. The time complexity remains O(n).

Space Complexity

The space complexity is O(1). The algorithm uses a fixed number of integer variables (ans, i, j, k) and these do not depend on the size of the input (wordsDict). There are no data structures that grow with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫