Jobs

Interviews

Discussions

Shortest Word Distance

Easy

Asked by:

6 views

Topics:

ArraysStringsTwo Pointers

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 * 10⁴
1 <= wordsDict[i].length <= 10
wordsDict[i] consists of lowercase English letters.
word1 and word2 are different.
word1 and word2 are both in the list.

Try coding it in LeetCode

Shortest Word Distance

Easy

Asked by:

6 views

Topics:

ArraysStringsTwo Pointers

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 * 10⁴
1 <= wordsDict[i].length <= 10
wordsDict[i] consists of lowercase English letters.
word1 and word2 are different.
word1 and word2 are both in the list.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can `word1` and `word2` be the same word?
If either `word1` or `word2` (or both) are not present in `wordsDict`, what should I return?
Can `wordsDict` be empty?
Are `word1` and `word2` guaranteed to be non-empty strings?
Is the `wordsDict` list mutable, or should I treat it as immutable?

Brute Force Solution

Approach

The goal is to find the smallest distance between two specific words in a list of words. The brute force method simply checks the distance between every possible pair of those two words in the list.

Here's how the algorithm would work step-by-step:

Look through the entire list of words, one by one.
Each time you find the first target word, remember its location.
Then, look through the entire list again to find the second target word.
Each time you find the second target word, calculate the distance between its location and the location of the first target word you found earlier.
Keep track of the shortest distance found so far.
Repeat steps 2-4 for every location where the first target word appears.
After checking all possible pairs, the shortest distance you kept track of is the answer.

Code Implementation

def shortest_word_distance_brute_force(words_list, word1, word2):
    minimum_distance = float('inf')

    for first_word_index in range(len(words_list)):
        if words_list[first_word_index] == word1:
            # Found an instance of word1, now find word2

            for second_word_index in range(len(words_list)):
                if words_list[second_word_index] == word2:
                    # Calculate distance and update minimum

                    current_distance = abs(first_word_index - second_word_index)
                    minimum_distance = min(minimum_distance, current_distance)

    return minimum_distance

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the list of words (of size n) to find the first target word. For each occurrence of the first word, the algorithm then iterates through the entire list of words again (of size n) to find the second target word and calculate the distance. This nested iteration results in a time complexity proportional to n * n, or n². Therefore, the overall time complexity is O(n²).

Space Complexity

O(1) – The provided algorithm only requires storing a few variables: the index of the first target word, the index of the second target word, and the shortest distance found so far. The number of these variables remains constant regardless of the number of words, N, in the input list. Therefore, the auxiliary space used is constant.

Optimal Solution

Approach

The most efficient way to find the shortest distance between two specific words in a list involves walking through the list only once. We keep track of the most recent positions where each of the two target words appears, updating the shortest distance whenever we find both words.

Here's how the algorithm would work step-by-step:

Remember the last position where word 1 was seen.
Remember the last position where word 2 was seen.
Go through the list of words one by one.
If the current word is word 1, update the remembered position for word 1.
If the current word is word 2, update the remembered position for word 2.
Whenever we have seen both word 1 and word 2 at least once, calculate the distance between their positions.
If this distance is shorter than any distance we've seen before, remember this new shortest distance.
After checking all the words, the shortest distance we remembered is the answer.

Code Implementation

def shortest_word_distance(words_list, word1, word2):
    last_position_word1 = -1
    last_position_word2 = -1
    shortest_distance = float('inf')

    for i, word in enumerate(words_list):
        if word == word1:
            last_position_word1 = i

        if word == word2:
            last_position_word2 = i

        # Need to check if both words have been found
        if last_position_word1 != -1 and last_position_word2 != -1:

            # Ensures correct calculation with absolute difference
            current_distance = abs(last_position_word1 - last_position_word2)

            # Update shortest distance if needed
            shortest_distance = min(shortest_distance, current_distance)

    return shortest_distance

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of words once, where n is the number of words in the list. Inside the loop, it performs constant-time operations: comparing the current word to the target words, updating indices, and calculating distances. Therefore, the time complexity is directly proportional to the number of words in the input list, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm uses a fixed number of variables to store the most recent positions of word1 and word2. These variables (index for word1 and index for word2, and shortest distance) consume a constant amount of memory, irrespective of the number of words in the input list, N. Therefore, the auxiliary space required does not depend on the input size and remains constant. This results in a space complexity of O(1).

Edge Cases

Case	How to Handle
wordsDict is null or empty	Return a large value like Integer.MAX_VALUE or throw an exception to indicate no distance is possible.
word1 or word2 is null or empty	Throw an IllegalArgumentException as it is not defined behavior
wordsDict contains only word1	Search for word2 and if it is not present, return Integer.MAX_VALUE
wordsDict contains only word2	Search for word1 and if it is not present, return Integer.MAX_VALUE
word1 and word2 are the same string	Find the two closest occurrences of the word and return the distance.
word1 or word2 is not present in wordsDict	Return Integer.MAX_VALUE since one of the words cannot be found.
Integer overflow with large index differences	Use long data type to store the distance to prevent potential integer overflow.
Large wordsDict size	Iterative solution will be more efficient than recursive calls and will handle a large input better.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can `word1` and `word2` be the same word?
If either `word1` or `word2` (or both) are not present in `wordsDict`, what should I return?
Can `wordsDict` be empty?
Are `word1` and `word2` guaranteed to be non-empty strings?
Is the `wordsDict` list mutable, or should I treat it as immutable?

Brute Force Solution

Approach

The goal is to find the smallest distance between two specific words in a list of words. The brute force method simply checks the distance between every possible pair of those two words in the list.

Here's how the algorithm would work step-by-step:

Look through the entire list of words, one by one.
Each time you find the first target word, remember its location.
Then, look through the entire list again to find the second target word.
Each time you find the second target word, calculate the distance between its location and the location of the first target word you found earlier.
Keep track of the shortest distance found so far.
Repeat steps 2-4 for every location where the first target word appears.
After checking all possible pairs, the shortest distance you kept track of is the answer.

Code Implementation

def shortest_word_distance_brute_force(words_list, word1, word2):
    minimum_distance = float('inf')

    for first_word_index in range(len(words_list)):
        if words_list[first_word_index] == word1:
            # Found an instance of word1, now find word2

            for second_word_index in range(len(words_list)):
                if words_list[second_word_index] == word2:
                    # Calculate distance and update minimum

                    current_distance = abs(first_word_index - second_word_index)
                    minimum_distance = min(minimum_distance, current_distance)

    return minimum_distance

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Remember the last position where word 1 was seen.
Remember the last position where word 2 was seen.
Go through the list of words one by one.
If the current word is word 1, update the remembered position for word 1.
If the current word is word 2, update the remembered position for word 2.
Whenever we have seen both word 1 and word 2 at least once, calculate the distance between their positions.
If this distance is shorter than any distance we've seen before, remember this new shortest distance.
After checking all the words, the shortest distance we remembered is the answer.

Code Implementation

def shortest_word_distance(words_list, word1, word2):
    last_position_word1 = -1
    last_position_word2 = -1
    shortest_distance = float('inf')

    for i, word in enumerate(words_list):
        if word == word1:
            last_position_word1 = i

        if word == word2:
            last_position_word2 = i

        # Need to check if both words have been found
        if last_position_word1 != -1 and last_position_word2 != -1:

            # Ensures correct calculation with absolute difference
            current_distance = abs(last_position_word1 - last_position_word2)

            # Update shortest distance if needed
            shortest_distance = min(shortest_distance, current_distance)

    return shortest_distance

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
wordsDict is null or empty	Return a large value like Integer.MAX_VALUE or throw an exception to indicate no distance is possible.
word1 or word2 is null or empty	Throw an IllegalArgumentException as it is not defined behavior
wordsDict contains only word1	Search for word2 and if it is not present, return Integer.MAX_VALUE
wordsDict contains only word2	Search for word1 and if it is not present, return Integer.MAX_VALUE
word1 and word2 are the same string	Find the two closest occurrences of the word and return the distance.
word1 or word2 is not present in wordsDict	Return Integer.MAX_VALUE since one of the words cannot be found.
Integer overflow with large index differences	Use long data type to store the distance to prevent potential integer overflow.
Large wordsDict size	Iterative solution will be more efficient than recursive calls and will handle a large input better.