algoadvance

Given a circular array of strings words and a string target, return the shortest distance between any occurrence of target and the starting index startIndex.

The circular array means that the next element of the last element is the first element, and the previous element of the first element is the last element.

Example:

words = ["hello","i","am","leetcode","hello"]
target = "hello"
startIndex = 1

Output:

1

Explanation: The shortest distance from index 1 (“i”) to the target “hello” is indeed 1 (circularly returning to the start).

Clarifying Questions

1. Q: Can the circular array contain duplicate elements of the target string?
   • A: Yes, the array can have multiple occurrences of the target string.
2. Q: What should we return if the target string is not found in the array?
   • A: We will assume the target string is always present in the array based on the given problem example.
3. Q: How should we handle an empty words list?
   • A: Since the problem assumes the presence of target in the array, an empty list is not applicable.

Strategy

1. Calculate Bidirectional Distance: For each index i where words[i] == target:
   • Calculate the forward distance from startIndex to i.
   • Calculate the backward distance from startIndex to i.
   • Keep track of the minimum distance found.
2. Forward Distance:
   • If i is greater than or equal to startIndex, it is simply i - startIndex.
   • If i is less than startIndex due to the circular nature, it would be len(words) - startIndex + i.
3. Backward Distance:
   • If startIndex is greater than or equal to i, it is startIndex - i.
   • If startIndex is less than i due to the circular nature, it would be startIndex + len(words) - i.
4. Return the minimum of all computed distances.

def shortest_distance_to_target(words, target, startIndex):
    n = len(words)
    min_distance = float('inf')
    
    for i in range(n):
        if words[i] == target:
            forward_distance = (i - startIndex) % n
            backward_distance = (startIndex - i) % n
            min_distance = min(min_distance, forward_distance, backward_distance)
    
    return min_distance

# Test Example
words = ["hello","i","am","leetcode","hello"]
target = "hello"
startIndex = 1

print(shortest_distance_to_target(words, target, startIndex))  # Should print 1

Time Complexity

• Time Complexity: O(n) where n is the length of the words array. We iterate through the list once to find all occurrences of the target.
• Space Complexity: O(1) since we only use a fixed amount of additional space for variables, regardless of the input size.

This method ensures that we find the shortest distance efficiently utilizing a linear scan of the array.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?