Skip to main content
Talentd

Shortest Distance to Target String in a Circular Array - Solution & Explanation

EasyArrayString14 min readAsked at: Amazon, Microsoft, Salesforce +1
Practice this problem

Problem Statement

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.

  • Formally, the next element of 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 <= 100
  • 1 <= words[i].length <= 100
  • words[i] and target consist of only lowercase English letters.
  • 0 <= startIndex < words.length

Approach Overview

Problem 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 1: Linear Search with Bidirectional Check

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Bidirectional Traversal from Start Index

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as at most, it checks each element once.
Space Complexity: O(1), due to no additional space use.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Linear Search with Bidirectional Check

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.

Bidirectional Traversal from Start Index

Time Complexity: O(n), as at most, it checks each element once.
Space Complexity: O(1), due to no additional space use.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear Search with Bidirectional Distance CalculationO(n)O(1)General solution; simple to implement and checks every occurrence of the target
Bidirectional Traversal from Start IndexO(n)O(1)Useful when the closest target may be near the start index; can terminate early

Video Solution

Shortest Distance to Target String in a Circular Array | Circular Trick | Leetcode 2515 | MIK • codestorywithMIK • 4,647 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Shortest Distance to Target String in a Circular Array easy or hard?
The problem is classified as Easy on LeetCode with about a 50% acceptance rate. The logic mainly tests understanding of circular arrays, index arithmetic, and basic iteration rather than advanced algorithms.
Shortest Distance to Target String in a Circular Array Python/Java solution
The solution is identical across languages: iterate through the array, compare each string with the target, and compute the circular distance. Python, Java, C++, and JavaScript implementations all run in O(n) time and use constant extra space.
How to solve Shortest Distance to Target String in a Circular Array in O(n)?
Iterate through the array and identify indices where the word equals the target. For each index compute the circular distance using min(abs(i - startIndex), n - abs(i - startIndex)). Keep the smallest value across all matches. If no match exists, return -1.
What is the best approach for Shortest Distance to Target String in a Circular Array?
The most common approach scans the array and computes the circular distance for every index where the target appears. For each match, calculate min(|i - startIndex|, n - |i - startIndex|) and track the smallest value. This runs in O(n) time with O(1) space and is easy to implement during interviews.
Is Shortest Distance to Target String in a Circular Array asked at Google/Amazon/Meta?
Circular array traversal and distance problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary in wording, the underlying idea—handling wrap‑around indices and computing minimal circular distance—is a common interview pattern.
What data structure is used in Shortest Distance to Target String in a Circular Array?
The primary data structure is a simple array of strings. The solution relies on index arithmetic and modulo operations to simulate circular traversal rather than using additional data structures.
What is the time complexity of Shortest Distance to Target String in a Circular Array?
The optimal time complexity is O(n), where n is the number of elements in the array. Every element may need to be checked to see if it matches the target. Space complexity is O(1) because the algorithm only stores a few variables for distance tracking.

Ready to solve this problem?

Practice Shortest Distance to Target String in a Circular Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Defuse the Bomb