Shortest Distance to Target String in a Circular Array

Difficulty: Easy | Acceptance: 65.20% | Paid: No Topics: Array, String

You are given a 0-indexed circular array words consisting of strings.

The following is a definition of a circular array:

• If words[i] is followed by words[i + 1] for all i in the range [0, words.length - 2], then words[words.length - 1] is followed by words[0].
• words[i] is followed by words[(i + 1) % words.length] for all i.

You are also given a string target. Starting from startIndex, you can move to either the next word or the previous word. At each step, you count one move.

Return the minimum number of moves needed to reach target. If it is impossible to reach target, return -1.

• Examples
• Constraints
• Brute Force Search
• Single Pass with Distance Calculation
• Collect Indices Then Calculate

Examples

Input: words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1
Output: 1
Explanation: From index 1, we can reach "hello" at index 0 by moving 1 step left.

Input: words = ["a","b","leetcode"], target = "leetcode", startIndex = 0
Output: 1
Explanation: From index 0, we can reach "leetcode" at index 2 by moving 2 steps right.

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

Constraints

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

Brute Force Search

Intuition Search outward from the starting index in both directions simultaneously, checking each position at increasing distances until we find the target.

Steps

• Check if the starting position already contains the target
• For each distance from 1 to n-1, check both clockwise and counter-clockwise positions
• Return the first distance where target is found
• Return -1 if target is never found

class Solution:
    def closetTarget(self, words: List[str], target: str, startIndex: int) -> int:
        n = len(words)
        if words[startIndex] == target:
            return 0
        
        for dist in range(1, n):
            if words[(startIndex + dist) % n] == target:
                return dist
            if words[(startIndex - dist + n) % n] == target:
                return dist
        
        return -1

Complexity

• Time: O(n) where n is the length of words array
• Space: O(1)
• Notes: Early termination possible when target is found close to start

Single Pass with Distance Calculation

Intuition Iterate through the array once, and for each occurrence of target, calculate the circular distance from startIndex using modular arithmetic.

Steps

• Initialize minimum distance to infinity
• Iterate through all indices in the array
• When target is found, calculate both clockwise and counter-clockwise distances
• Update minimum distance with the smaller of the two
• Return minimum distance or -1 if target not found

class Solution:
    def closetTarget(self, words: List[str], target: str, startIndex: int) -> int:
        n = len(words)
        min_dist = float('inf')
        
        for i, word in enumerate(words):
            if word == target:
                clockwise_dist = (i - startIndex) % n
                counter_dist = (startIndex - i) % n
                min_dist = min(min_dist, clockwise_dist, counter_dist)
        
        return min_dist if min_dist != float('inf') else -1

Complexity

• Time: O(n) where n is the length of words array
• Space: O(1)
• Notes: Always iterates through entire array even if target is found early

Collect Indices Then Calculate

Intuition First collect all indices where target appears, then find the minimum circular distance from startIndex to any of these indices.

Steps

• Iterate through array and collect all indices where target is found
• If no indices found, return -1
• For each collected index, calculate both clockwise and counter-clockwise distances
• Return the minimum distance found

class Solution:
    def closetTarget(self, words: List[str], target: str, startIndex: int) -> int:
        n = len(words)
        target_indices = []
        
        for i, word in enumerate(words):
            if word == target:
                target_indices.append(i)
        
        if not target_indices:
            return -1
        
        min_dist = float('inf')
        for idx in target_indices:
            clockwise_dist = (idx - startIndex) % n
            counter_dist = (startIndex - idx) % n
            min_dist = min(min_dist, clockwise_dist, counter_dist)
        
        return min_dist

Complexity

• Time: O(n) where n is the length of words array
• Space: O(k) where k is the number of target occurrences
• Notes: Uses extra space to store indices but can be useful if multiple queries needed