2515. Shortest Distance to Target String in a Circular Array

Array
String

TIME

O(n)

SPACE

O(1)

Intuition

For each occurrence of target, compute the minimum of clockwise and counter-clockwise distances. Return the overall minimum.

Solution

For a circular array of length n, the distance from start to index i:

Clockwise: (i - start + n) % n
Counter-clockwise: (start - i + n) % n
Shortest: min(clockwise, n - clockwise)

for i, word in enumerate(words):
    if word == target:
        clockwise = (i - startIndex + n) % n
        min_dist = min(min_dist, clockwise, n - clockwise)

Complexity

Time: O(n × m) where m = average word length (for string comparison)
Space: O(1)

Edge Cases

Target not in array → return -1
Target at startIndex → return 0
Multiple occurrences of target → pick closest
Single element array with target → return 0

Code

from typing import List


class Solution:
    def closetTarget(self, words: List[str], target: str, startIndex: int) -> int:
        """
        2515. Shortest Distance to Target String in a Circular Array
        Time: O(n)
        Space: O(1)
        """
        n = len(words)
        min_dist = float('inf')

        for i, word in enumerate(words):
            if word == target:
                clockwise = (i - startIndex + n) % n
                counter_clockwise = n - clockwise
                min_dist = min(min_dist, clockwise, counter_clockwise)

        return min_dist if min_dist != float('inf') else -1

import java.util.List;

/**
 * 2515. Shortest Distance to Target String in a Circular Array
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int closetTarget(String[] words, String target, int startIndex) {
        int n = words.length;
        int minDist = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            if (words[i].equals(target)) {
                int clockwise = (i - startIndex + n) % n;
                int counterClockwise = n - clockwise;
                minDist = Math.min(minDist, Math.min(clockwise, counterClockwise));
            }
        }

        return minDist == Integer.MAX_VALUE ? -1 : minDist;
    }
}