leetcode solution

LeetCode 2515 Python Solution: Shortest Distance in Circular Array

by

Problem Summary

You are given:

  • a circular array words
  • a starting index startIndex
  • a string target

You need to find the shortest distance from startIndex to any index where words[i] == target.

Because the array is circular, you can move:

  • forward: (i + 1) % n
  • backward: (i - 1 + n) % n

If the target does not exist, return -1.

Key Observation

For every index i where words[i] == target, the circular distance from startIndex is:

  • direct distance: abs(i - startIndex)
  • wrap-around distance: n - abs(i - startIndex)

So the shortest circular distance is:

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

We compute this for every matching index and take the minimum.

Approach

  1. Let n = words.length
  2. Initialize answer as a large value
  3. Traverse the array
  4. For each index i where words[i] == target:
    • compute d = abs(i - startIndex)
    • circular distance = min(d, n - d)
    • update answer
  5. If no match was found, return -1

Example

Input

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

Matching indices

  • 0
  • 4

Distances

From index 1 to 0:

abs(0 - 1) = 1
circular distance = min(1, 5 - 1) = 1

From index 1 to 4:

abs(4 - 1) = 3
circular distance = min(3, 5 - 3) = 2

Minimum distance is 1.

Output

1

Python Solution

class Solution:
    def closetTarget(self, words: List[str], target: str, startIndex: int) -> int:
        n = len(words)
        ans = float("inf")

        for i, word in enumerate(words):
            if word == target:
                d = abs(i - startIndex)
                ans = min(ans, min(d, n - d))

        return -1 if ans == float("inf") else ans

Why This Works

The array is circular, so between two indices there are always two possible paths:

  • clockwise
  • counterclockwise

If the direct distance is d, then the wrapped distance is n - d.

Taking min(d, n - d) gives the true shortest circular distance.

Checking every occurrence of target guarantees we find the global minimum.

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)

Conclusion

This problem is simple once you recognize the circular distance formula:

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

Then it becomes a straightforward linear scan.

For this problem, brute force is already optimal.

If you want, I can also turn this into a more polished blog-style article with intro, intuition, dry run, and interview tips.

Leave a Comment