Shortest Distance to Target String in a Circular Array solution and explanation
9 more videos on this problem
Shortest Distance to Target String in a Circular Array | Circular Trick | Leetcode 2515 | MIKcodestorywithMIK · 11:53 · 4K views
Shortest Distance to Target String in a Circular Array | Leetcode 2515Tech Courses · 7:58 · 1K views
Shortest Distance to Target String in a Circular Array | 2515 LeetCode | Leetcode Weekly Contest 325CodeWithSunny · 8:48 · 1K views
Leetcode Weekly contest 325 - Easy - Shortest Distance to Target String in a Circular ArrayPrakhar Agrawal · 5:20 · 624 views
LeetCode 2515. Shortest Distance to Target String in a Circular Array - Interview Prep Ep 125Fisher Coder · 16:05 · 542 views
2515. Shortest Distance to Target String in a Circular Array (Leetcode Easy)Programming Live with Larry · 5:20 · 454 views
2515. Shortest Distance to Target String in a Circular Array | Leetcode Daily - PythonLeetcode Daily · 5:23 · 348 views
Daily Leetcode #2206: Apr 15, 2026 - 2515. Shortest Distance to Target String in a Circular ArrayProgramming Live with Larry · 4:54 · 146 views
Shortest Distance to Target String in a Circular Array | LeetCode 2515 - Pythonimpoldev · 7:03 · 117 views
Shortest Distance to Target String in a Circular Array | LeetCode 2515 | Java Code | Developer CoderDeveloper Coder · 9:08 · 106 views
The problem
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]iswords[(i + 1) % n]and the previous element ofwords[i]iswords[(i - 1 + n) % n], wherenis the length ofwords.
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]andtargetconsist 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.
def shortestDistance(words, target, startIndex):
min_distance = float('inf')
n = len(words)
for i, word in enumerate(words):
if word == target:
distance = abs(i - startIndex)
circular_distance = n - distance
min_distance = min(min_distance, min(distance, circular_distance))
return -1 if min_distance == float('inf') else min_distance
words = ["hello", "i", "am", "leetcode", "hello"]
print(shortestDistance(words, "hello", 1))import java.util.*;
public class Solution {
public int shortestDistance(String[] words, String target, int startIndex) {
int minDistance = Integer.MAX_VALUE;
int n = words.length;
for (int i = 0; i < n; i++) {
if (words[i].equals(target)) {
int distance = Math.abs(i - startIndex);
int circularDistance = n - distance;
minDistance = Math.min(minDistance, Math.min(distance, circularDistance));
}
}
return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
}
public static void main(String[] args) {
Solution sol = new Solution();
String[] words = {"hello", "i", "am", "leetcode", "hello"};
int result = sol.shortestDistance(words, "hello", 1);
System.out.println(result);
}
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int shortestDistance(vector<string>& words, string target, int startIndex) {
int minDistance = INT_MAX;
int n = words.size();
for (int i = 0; i < n; ++i) {
if (words[i] == target) {
int distance = abs(i - startIndex);
int circularDistance = n - distance;
minDistance = min(minDistance, min(distance, circularDistance));
}
}
return minDistance == INT_MAX ? -1 : minDistance;
}
int main() {
vector<string> words = {"hello", "i", "am", "leetcode", "hello"};
string target = "hello";
int startIndex = 1;
cout << shortestDistance(words, target, startIndex) << endl;
return 0;
}function shortestDistance(words, target, startIndex) {
let minDistance = Infinity;
let n = words.length;
for (let i = 0; i < n; i++) {
if (words[i] === target) {
let distance = Math.abs(i - startIndex);
let circularDistance = n - distance;
minDistance = Math.min(minDistance, Math.min(distance, circularDistance));
}
}
return minDistance === Infinity ? -1 : minDistance;
}
let words = ["hello", "i", "am", "leetcode", "hello"];
console.log(shortestDistance(words, "hello", 1));#include <stdio.h>
#include <string.h>
#include <limits.h>
int shortestDistance(char* words[], int wordsSize, char* target, int startIndex) {
int minDistance = INT_MAX;
for (int i = 0; i < wordsSize; i++) {
if (strcmp(words[i], target) == 0) {
int distance = abs(i - startIndex);
int circularDistance = wordsSize - distance;
minDistance = fmin(minDistance, fmin(distance, circularDistance));
}
}
return minDistance == INT_MAX ? -1 : minDistance;
}
int main() {
char* words[] = {"hello", "i", "am", "leetcode", "hello"};
int wordsSize = 5;
char* target = "hello";
int startIndex = 1;
int result = shortestDistance(words, wordsSize, target, startIndex);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int ShortestDistance(string[] words, string target, int startIndex) {
int minDistance = int.MaxValue;
int n = words.Length;
for (int i = 0; i < n; i++) {
if (words[i] == target) {
int distance = Math.Abs(i - startIndex);
int circularDistance = n - distance;
minDistance = Math.Min(minDistance, Math.Min(distance, circularDistance));
}
}
return minDistance == int.MaxValue ? -1 : minDistance;
}
public static void Main() {
var solution = new Solution();
string[] words = {"hello", "i", "am", "leetcode", "hello"};
Console.WriteLine(solution.ShortestDistance(words, "hello", 1));
}
}The Python solution performs a linear search over the list of words to locate matches to the target string. Upon finding a match, it evaluates both the direct and circular distances, updating the minimum distance accordingly. It returns the smallest distance found.
Time Complexity: O(n), where n is the length of the list.
Space Complexity: O(1), as it only uses a fixed amount of auxiliary space.
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.
def shortestDistance(words, target, startIndex):
n = len(words)
for distance in range(n):
forwardIndex = (startIndex + distance) % n
backwardIndex = (startIndex - distance + n) % n
if words[forwardIndex] == target or words[backwardIndex] == target:
return distance
return -1
words = ["hello", "i", "am", "leetcode", "hello"]
print(shortestDistance(words, "hello", 1))public class Solution {
public int shortestDistance(String[] words, String target, int startIndex) {
int n = words.length;
for (int distance = 0; distance < n; distance++) {
int forwardIndex = (startIndex + distance) % n;
int backwardIndex = (startIndex - distance + n) % n;
if (words[forwardIndex].equals(target) || words[backwardIndex].equals(target)) {
return distance;
}
}
return -1;
}
public static void main(String[] args) {
Solution sol = new Solution();
String[] words = {"hello", "i", "am", "leetcode", "hello"};
System.out.println(sol.shortestDistance(words, "hello", 1));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int shortestDistance(vector<string>& words, string target, int startIndex) {
int n = words.size();
for (int distance = 0; distance < n; ++distance) {
int forwardIndex = (startIndex + distance) % n;
int backwardIndex = (startIndex - distance + n) % n;
if (words[forwardIndex] == target || words[backwardIndex] == target) {
return distance;
}
}
return -1;
}
int main() {
vector<string> words = {"hello", "i", "am", "leetcode", "hello"};
cout << shortestDistance(words, "hello", 1) << endl;
return 0;
}function shortestDistance(words, target, startIndex) {
let n = words.length;
for (let distance = 0; distance < n; distance++) {
let forwardIndex = (startIndex + distance) % n;
let backwardIndex = (startIndex - distance + n) % n;
if (words[forwardIndex] === target || words[backwardIndex] === target) {
return distance;
}
}
return -1;
}
let words = ["hello", "i", "am", "leetcode", "hello"];
console.log(shortestDistance(words, "hello", 1));#include <stdio.h>
#include <string.h>
int shortestDistance(char* words[], int wordsSize, char* target, int startIndex) {
for (int distance = 0; distance < wordsSize; ++distance) {
int forwardIndex = (startIndex + distance) % wordsSize;
int backwardIndex = (startIndex - distance + wordsSize) % wordsSize;
if (strcmp(words[forwardIndex], target) == 0 || strcmp(words[backwardIndex], target) == 0) {
return distance;
}
}
return -1;
}
int main() {
char* words[] = {"hello", "i", "am", "leetcode", "hello"};
int wordsSize = 5;
char* target = "hello";
int startIndex = 1;
int result = shortestDistance(words, wordsSize, target, startIndex);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int ShortestDistance(string[] words, string target, int startIndex) {
int n = words.Length;
for (int distance = 0; distance < n; distance++) {
int forwardIndex = (startIndex + distance) % n;
int backwardIndex = (startIndex - distance + n) % n;
if (words[forwardIndex] == target || words[backwardIndex] == target) {
return distance;
}
}
return -1;
}
public static void Main() {
var solution = new Solution();
string[] words = {"hello", "i", "am", "leetcode", "hello"};
Console.WriteLine(solution.ShortestDistance(words, "hello", 1));
}
}The Python solution methodically checks two symmetrical paths—one forward, one backward—and compares index matches against the target for a nearest match, halting early once found.
Time Complexity: O(n), looping at most once through each element.
Space Complexity: O(1), without additional storage demands.
Approach 3: Default Approach
function closetTarget(words: string[], target: string, startIndex: number): number {
const n = words.length;
for (let i = 0; i <= n >> 1; i++) {
if (words[(startIndex - i + n) % n] === target || words[(startIndex + i) % n] === target) {
return i;
}
}
return -1;
}func closetTarget(words []string, target string, startIndex int) int {
n := len(words)
ans := n
for i, w := range words {
if w == target {
t := abs(i - startIndex)
ans = min(ans, min(t, n-t))
}
}
if ans == n {
return -1
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn closet_target(words: Vec<String>, target: String, start_index: i32) -> i32 {
let start_index = start_index as usize;
let n = words.len();
for i in 0..=n >> 1 {
if words[(start_index - i + n) % n] == target || words[(start_index + i) % n] == target
{
return i as i32;
}
}
-1
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Linear Search with Bidirectional Check | Time Complexity: O(n), where n is the length of the list. |
| Bidirectional Traversal from Start Index | Time Complexity: O(n), looping at most once through each element. |
| Default Approach | – |
Complexity analysis
| 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 |
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.