Shortest Distance to Target String in a Circular Array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def closetTarget(self, words, target, startIndex):
        n = len(words)

        if target not in words:
            return -1

        # calculate distance in forward direction
        forward_distance = 0
        for i in range(startIndex, startIndex + n):
            if words[i % n] == target:
                break
            forward_distance += 1

        # calculate distance in backward direction
        backward_distance = 0
        for i in range(startIndex, startIndex - n, -1):
            if words[i % n] == target:
                break
            backward_distance += 1

        # return minimum of forward and backward distances
        return min(forward_distance, backward_distance)

The Python function closetTarget is designed to find the minimum distance to a target word in a circular list of words. The list is circular in the sense that after the last word, the first word follows.

Here’s how the function works:

1. It starts by checking whether the target word exists in the list. If it doesn’t exist, the function returns -1.

2. It initializes two variables, forward_distance and backward_distance, to store the distances to the target word when moving forward and backward in the list, respectively.

3. It then iterates over the list in the forward direction starting from startIndex, incrementing forward_distance until it finds the target word. The operation i % n ensures that the index wraps around to the beginning of the list after reaching the end.

4. It does the same in the backward direction, decrementing the index from startIndex and incrementing backward_distance until it finds the target word.

5. Finally, it returns the minimum of forward_distance and backward_distance, which is the minimum distance to the target word in the circular list.

The function effectively uses the property of modulo operation to handle circular lists and calculates distances in two directions in a single pass, resulting in a time complexity of O(n), where n is the number of words in the list. The space complexity is O(1) as no extra space is used apart from the input list.

One Pass

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def closetTarget(self, words, target, startIndex):
        res = float('inf')  # equivalent to Integer.MAX_VALUE in Java
        n = len(words)

        for i in range(len(words)):
            if words[i] == target:
                d = abs(i - startIndex)
                res = min(res, d, n - d)

        return -1 if res == float('inf') else res

The Python function closetTarget is designed to find the minimum distance to a target word in a circular list of words. The list is circular in that after the last word, the first word follows.

Here’s how the function works:

1. It starts by initializing the result res to positive infinity. This acts as a placeholder for the minimum distance, which will be updated as we find instances of the target word.

2. It then iterates over the list of words. For each word, if it is equal to the target, it calculates the distance d from the current index to startIndex (the absolute difference between the two indices).

3. In a circular list, a word can be reached either by moving forward from startIndex or by moving backward. So, it also calculates n - d, which is the distance when moving in the opposite direction.

4. It updates res to be the minimum of its current value, d, and n - d. This ensures that res always holds the smallest possible distance to the target word.

5. Finally, if res is still positive infinity (meaning the target word was not found), it returns -1. Otherwise, it returns res.

This function effectively uses the property of circular lists to calculate distances in both directions in a single pass, resulting in a time complexity of O(n), where n is the number of words in the list. The space complexity is O(1) as no extra space is used apart from the input list.