Shortest Distance to Target String in a Circular Array

Intuition

The only positions that matter are the indices where words[index] == target.

If we know one such index, then there are always two ways to reach it from startIndex in a circular array:

• move directly across the array
• wrap around the other side

So for every matching index, the distance is:

min(abs(index - startIndex), n - abs(index - startIndex))

We compute this for every occurrence of target and keep the minimum answer.

Approach: Traversal

Let n be the size of the array.

We scan the array once from left to right:

1. If words[index] is not target, skip it
2. If it matches, compute the normal distance abs(index - startIndex)
3. Convert that into the circular distance using min(distance, n - distance)
4. Update the best answer

If we never find target, the answer stays invalid and we return -1.

class Solution {
    public int closetTarget(String[] words, String target, int startIndex) {
        int n = words.length;
        int answer = n;

        for (int index = 0; index < n; index++) {
            if (words[index].equals(target)) {
                int distance = Math.abs(index - startIndex);
                answer = Math.min(answer, Math.min(distance, n - distance));
            }
        }

        return answer < n ? answer : -1;
    }
}

Dry run

Take:

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

Here n = 5.

Matching positions for target are:

• index 0
• index 4

For index 0:

• direct distance = abs(0 - 1) = 1
• wrap distance = 5 - 1 = 4
• best = 1

For index 4:

• direct distance = abs(4 - 1) = 3
• wrap distance = 5 - 3 = 2
• best = 2

The minimum among all matching positions is 1, so the answer is 1.

Why this works

Any valid path must end at an index where the word equals target.

For each such index, the shortest circular path is either:

• the forward/backward direct distance
• or the wrapped distance through the other end of the array

The formula min(distance, n - distance) checks both possibilities, so it gives the true shortest distance for that index. Since we evaluate every index containing target, the minimum value we keep is the overall shortest distance.

Complexity Analysis

Time Complexity: O(n * L)

• we scan all n words once
• comparing a word with target can take up to O(L)

Space Complexity: O(1)