You are given a 0-indexed circular string array words and a string target. A circular array means that the array's end connects to the array's beginning.
words[i] is words[(i + 1) % n] and the previous element of words[i] is words[(i - 1 + n) % n], where n is the length of words.Starting from startIndex, you can move to either the next word or the previous word with 1 step at a time.
Return the shortest distance needed to reach the string target. If the string target does not exist in words, return -1.
Example 1:
Input: words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1 Output: 1 Explanation: We start from index 1 and can reach "hello" by - moving 3 units to the right to reach index 4. - moving 2 units to the left to reach index 4. - moving 4 units to the right to reach index 0. - moving 1 unit to the left to reach index 0. The shortest distance to reach "hello" is 1.
Example 2:
Input: words = ["a","b","leetcode"], target = "leetcode", startIndex = 0 Output: 1 Explanation: We start from index 0 and can reach "leetcode" by - moving 2 units to the right to reach index 3. - moving 1 unit to the left to reach index 3. The shortest distance to reach "leetcode" is 1.
Example 3:
Input: words = ["i","eat","leetcode"], target = "ate", startIndex = 0
Output: -1
Explanation: Since "ate" does not exist in words, we return -1.
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 100words[i] and target consist of only lowercase English letters.0 <= startIndex < words.lengthProblem Overview: You are given a circular array of strings, a target string, and a starting index. The task is to find the minimum distance from the start index to any occurrence of the target while moving either left or right around the circle. Because the array is circular, moving past the end wraps back to the beginning.
Approach 1: Linear Search with Bidirectional Check (O(n) time, O(1) space)
Scan the entire array and locate every index where words[i] == target. For each match, compute the circular distance from startIndex. In a circular array the distance can be measured in two ways: forward distance |i - startIndex| and the wrap-around distance n - |i - startIndex|. The minimum of these two values gives the actual circular distance. Track the smallest distance across all matches. This approach works well because it directly evaluates every possible target position in a single pass through the array. It uses constant extra space and only basic iteration over the array. If the target never appears, return -1.
Approach 2: Bidirectional Traversal from Start Index (O(n) time, O(1) space)
Instead of scanning the entire array first, expand outward from the startIndex step by step in both directions. For step d, check (startIndex + d) % n for the clockwise direction and (startIndex - d + n) % n for the counterclockwise direction. As soon as either position contains the target, return d. This works because the first match encountered during this outward expansion must be the minimum circular distance. The modulo arithmetic handles the circular wrapping. The method avoids unnecessary checks once the closest occurrence is found, which can reduce average work when the target is near the starting position. It relies on simple index math and comparisons on string values.
Recommended for interviews: Both approaches run in O(n) time with O(1) space, which is optimal since every element might need inspection. Interviewers typically expect the linear scan with circular distance calculation because it is straightforward and easy to reason about. The bidirectional traversal demonstrates stronger intuition about circular arrays and can return earlier when the target is close to the starting index. Showing the brute-force scan first and then discussing the outward traversal highlights clear problem‑solving progression.
In this approach, we iterate over the array to find the indices of the target. Once we identify the indices, we calculate the shortest distance bidirectionally from the startIndex to reach those indices in the circular manner.
This code performs a linear search to identify indices where the target matches any element in the circular string array. For each match, it calculates both direct and reverse (circular) distances from the startIndex, selecting the minimum of both options as the potential shortest path.
Time Complexity: O(n), where n is the length of the array, since it needs to inspect every element.
Space Complexity: O(1), as it uses constant space.
Rather than iterating the entire list, this approach involves expanding from the startIndex while checking both the left and right paths simultaneously, leveraging the known circular nature of the array.
This code explores two paths simultaneously: moving forward and backward from the starting index. By doing so, it quickly identifies the presence and position of the target string and returns the shortest distance quickly.
Time Complexity: O(n), as at most, it checks each element once.
Space Complexity: O(1), due to no additional space use.
| Approach | Complexity |
|---|---|
| Linear Search with Bidirectional Check | Time Complexity: O(n), where n is the length of the array, since it needs to inspect every element. |
| Bidirectional Traversal from Start Index | Time Complexity: O(n), as at most, it checks each element once. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Search with Bidirectional Distance Calculation | O(n) | O(1) | General solution; simple to implement and checks every occurrence of the target |
| Bidirectional Traversal from Start Index | O(n) | O(1) | Useful when the closest target may be near the start index; can terminate early |
Shortest Distance to Target String in a Circular Array | 2515 LeetCode | Leetcode Weekly Contest 325 • CodeWithSunny • 1,147 views views
Watch 9 more video solutions →Practice Shortest Distance to Target String in a Circular Array with our built-in code editor and test cases.
Practice on FleetCode