Shortest Distance to Target String in a Circular Array

#280 Most AskedEasy

Shortest Distance to Target String in a Circular Array #280 Most Asked

Easy

12 views

Topics:

ArraysStringsTwo Pointers

You are given a 0-indexed circular string array words and a string target. A circular array means that the array's end connects to the array's beginning.

Formally, the next element of words[i] is words[(i + 1) % n] and the previous element of words[i] is words[(i - 1 + n) % n], where n is the length of words.

Starting from startIndex, you can move to either the next word or the previous word with 1 step at a time.

Return the shortest distance needed to reach the string target. If the string target does not exist in words, return -1.

Example 1:

Input: words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1
Output: 1
Explanation: We start from index 1 and can reach "hello" by
- moving 3 units to the right to reach index 4.
- moving 2 units to the left to reach index 4.
- moving 4 units to the right to reach index 0.
- moving 1 unit to the left to reach index 0.
The shortest distance to reach "hello" is 1.

Example 2:

Input: words = ["a","b","leetcode"], target = "leetcode", startIndex = 0
Output: 1
Explanation: We start from index 0 and can reach "leetcode" by
- moving 2 units to the right to reach index 3.
- moving 1 unit to the left to reach index 3.
The shortest distance to reach "leetcode" is 1.

Example 3:

Input: words = ["i","eat","leetcode"], target = "ate", startIndex = 0
Output: -1
Explanation: Since "ate" does not exist in words, we return -1.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] and target consist of only lowercase English letters.
0 <= startIndex < words.length

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:

What is the range for the length of the `words` array, and are there any constraints on the length of each string within the array?
If the `target` string does not exist in the `words` array, what should I return?
Are the strings in the `words` array case-sensitive? Should I perform a case-insensitive comparison with the `target`?
Can the `words` array contain null or empty strings? If so, how should I handle them?
Are there any specific constraints on the characters that can appear in the strings (e.g., only ASCII characters)?

Brute Force Solution

Approach

The brute force way to find the shortest distance involves checking every possible starting point in the word list and then looking in both directions around the circle. We continue doing this until we find the target word. We then remember the shortest trip we had to take.

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

Start with the first word in the list.
Look at the words going forward one by one until you find the target word. Count how many steps it took.
Look at the words going backward one by one until you find the target word. Remember to 'wrap around' to the end of the list if you go past the beginning. Count how many steps it took.
Compare how many steps forward and backward took and save the smaller number of steps.
Now, do the same thing, but start with the second word in the list.
Keep repeating this process, starting with each word in the list one at a time.
At the end, compare all the smallest numbers of steps you saved from each starting word. Pick the smallest number overall. This is the shortest distance to the target word.

Code Implementation

def shortest_distance_brute_force(circular_array, target_word):

    array_length = len(circular_array)
    shortest_distances = []

    for start_index in range(array_length):
        # Iterate through each word in the array as a starting point.

        for direction in [-1, 1]: # Check both directions
            current_distance = 0
            current_index = start_index

            while True:
                if circular_array[current_index] == target_word:
                    shortest_distances.append(current_distance)
                    break #Target found, break inner loop

                current_distance += 1
                current_index = (current_index + direction) % array_length

                # Avoid infinite loops if target not found.
                if current_distance >= array_length:
                    break

    # Avoid returning min of empty list
    if not shortest_distances:
        return -1

    return min(shortest_distances)

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n words in the word list as a starting point. For each starting point, it searches forward and backward through the list until the target is found, potentially visiting each of the n words in the worst case. Therefore, in the worst case, the algorithm performs n searches, each potentially requiring up to n steps. This results in a time complexity of O(n*n), which simplifies to O(n²).

Space Complexity

O(1) – The algorithm described only uses a few constant space variables like loop counters and to store the minimum distance found so far. The number of these variables does not depend on the size of the input word list (N). Therefore, the auxiliary space required is constant, resulting in O(1) space complexity.

Optimal Solution

Approach

The key to efficiently solving this problem lies in realizing that we only need to consider two possible directions to find the target word from the starting word. We can calculate the distance in both directions and choose the shorter one. This avoids checking every single position in the array.

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

Identify the positions of the target word within the list.
For each target word position, calculate the distance to it by moving forward in the list.
For each target word position, also calculate the distance by moving backward in the list (going around the end to the start if needed).
Compare the forward and backward distances for each target word and keep the shortest of the two.
From all the shortest distances that you found, find the absolute shortest distance to any target word in either direction.

Code Implementation

def shortest_distance(word_list, start_word, target_word):
    list_length = len(word_list)
    start_index = -1
    
    for i in range(list_length):
        if word_list[i] == start_word:
            start_index = i
            break

    if start_index == -1:
        return -1

    forward_distance = 0
    backward_distance = 0
    forward_index = start_index
    backward_index = start_index

    # Find the forward distance to the target word.
    while forward_distance < list_length:
        if word_list[forward_index] == target_word:
            break
        forward_index = (forward_index + 1) % list_length
        forward_distance += 1

    # Find the backward distance to the target word.
    while backward_distance < list_length:
        if word_list[backward_index] == target_word:
            break
        
        backward_index = (backward_index - 1 + list_length) % list_length

        backward_distance += 1

    # Check if the target word exists in the list
    if forward_distance == list_length and backward_distance == list_length:
        return -1

    # Compare forward and backward distances to determine the shortest path.
    return min(forward_distance, backward_distance)

Big(O) Analysis

Time Complexity

O(n) – The algorithm first identifies target word positions, which takes O(n) time in the worst case, where n is the length of the array. Then, for each target position (at most n), it calculates the forward and backward distances from the start index, both of which take constant time O(1). Since these constant-time operations are performed at most n times based on identified target positions, the overall time complexity remains dominated by the initial search for target positions, resulting in O(n).

Space Complexity

O(N) – The space complexity is O(N) because in step 1, we identify the positions of the target word within the list and store these positions. In the worst case, every word in the list could be the target word, thus creating an auxiliary list of size N, where N is the length of the input list. The rest of the steps use a constant amount of extra space for calculations, so the dominant space usage is from storing the target word positions.

Edge Cases

Case	How to Handle
words array is null or empty	Return an empty array or an array filled with -1 (or a similar sentinel value) to indicate no solution since no words exist.
target string is null or empty	Return an array filled with the length of the words array, as no target exists and thus every word is effectively maximally distant.
words array contains only one element	If the single element matches the target, return [0]; otherwise return [1].
target string does not exist in the words array	Return an array filled with the length of the `words` array, indicating maximum possible distance for each element.
target string appears multiple times in the words array	The solution should find the minimum distance among all occurrences of the target.
words array contains very long strings	String comparison needs to be efficient, and consider possible memory consumption if strings are extremely long but doesn't fundamentally change the distance calculation.
words array has a large number of words (e.g., exceeding memory constraints).	Consider optimizing for memory by iterating through the array and calculating the shortest distances on-the-fly instead of storing all target indices beforehand, and if absolutely necessary break up the large array into manageable chunks.
words array contains duplicate strings, and the target is one of them.	The algorithm should correctly calculate distances to all occurrences, even if some are at the same string value but distinct positions.

words array is null or empty

How to Handle:

Return an empty array or an array filled with -1 (or a similar sentinel value) to indicate no solution since no words exist.

target string is null or empty

How to Handle:

Return an array filled with the length of the words array, as no target exists and thus every word is effectively maximally distant.

words array contains only one element

How to Handle:

If the single element matches the target, return [0]; otherwise return [1].

target string does not exist in the words array

How to Handle:

Return an array filled with the length of the `words` array, indicating maximum possible distance for each element.

target string appears multiple times in the words array

How to Handle:

The solution should find the minimum distance among all occurrences of the target.

words array contains very long strings

How to Handle:

String comparison needs to be efficient, and consider possible memory consumption if strings are extremely long but doesn't fundamentally change the distance calculation.

words array has a large number of words (e.g., exceeding memory constraints).

How to Handle:

Consider optimizing for memory by iterating through the array and calculating the shortest distances on-the-fly instead of storing all target indices beforehand, and if absolutely necessary break up the large array into manageable chunks.

words array contains duplicate strings, and the target is one of them.

How to Handle:

The algorithm should correctly calculate distances to all occurrences, even if some are at the same string value but distinct positions.