Watch 10 video solutions for Shortest Distance to Target String in a Circular Array, a easy level problem involving Array, String. This walkthrough by CodeWithSunny has 1,147 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |