Shortest Distance to Target String in a Circular Array

Shortest Distance to Target String in a Circular Array - Problem

Array String Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: words = ["happy","sad","corner","leetcode","pass","around"], target = "leetcode", startIndex = 1

› Output: 2

💡 Note: From index 1 ("sad"), we can reach "leetcode" at index 3 by moving 2 steps clockwise (1→2→3) or 4 steps counterclockwise (1→0→5→4→3). The minimum is 2.

Example 2 — Target at Start

$ Input: words = ["a","b","c"], target = "a", startIndex = 0

› Output: 0

💡 Note: The target "a" is already at the starting position (index 0), so the distance is 0.

Example 3 — Target Not Found

$ Input: words = ["i","eat","code"], target = "day", startIndex = 1

› Output: -1

💡 Note: The target "day" does not exist in the array, so 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

Visualization

Tap to expand

Understanding the Visualization

Input

Circular array with words, target string, and start index

Process

Search both clockwise and counterclockwise directions

Output

Return minimum steps needed, or -1 if not found

Key Takeaway

🎯 Key Insight: In a circular array, always check both directions and choose the shorter path

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that in a circular array, we can reach any element by moving in two directions - clockwise or counterclockwise. The optimal approach is to find all occurrences of the target and calculate the minimum circular distance. Best approach is the optimized single-pass solution. Time: O(n), Space: O(k) where k is the number of target occurrences.

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search Both Directions	O(n)	O(1)	Search clockwise and counterclockwise separately, return minimum distance
Single Pass with Distance Calculation	O(n)	O(k)	Find all occurrences in one pass, calculate minimum circular distance

Linear Search Both Directions — Algorithm Steps

Search clockwise from startIndex until target is found or we complete the circle
Search counterclockwise from startIndex until target is found or we complete the circle
Return the minimum of both distances, or -1 if target not found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Begin at startIndex

Search Both Ways

Check clockwise and counterclockwise

Return Minimum

Return the shorter distance found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char words[][100], int n, char* target, int startIndex) {
    // Search clockwise
    int clockwiseDist = -1;
    for (int i = 0; i < n; i++) {
        int idx = (startIndex + i) % n;
        if (strcmp(words[idx], target) == 0) {
            clockwiseDist = i;
            break;
        }
    }
    
    // If target not found, return -1
    if (clockwiseDist == -1) {
        return -1;
    }
    
    // Search counterclockwise
    int counterclockwiseDist = -1;
    for (int i = 0; i < n; i++) {
        int idx = (startIndex - i + n) % n;
        if (strcmp(words[idx], target) == 0) {
            counterclockwiseDist = i;
            break;
        }
    }
    
    // Return minimum distance
    return (clockwiseDist < counterclockwiseDist) ? clockwiseDist : counterclockwiseDist;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    char words[100][100];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        // Remove quotes and spaces
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"' || *end == '\n')) {
            *end = '\0';
            end--;
        }
        if (strlen(token) > 0) {
            strcpy(words[n], token);
            n++;
        }
        token = strtok(NULL, ",");
    }
    
    char target[100];
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    
    int startIndex;
    scanf("%d", &startIndex);
    
    int result = solution(words, n, target, startIndex);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

In worst case, we search the entire array in both directions

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track indices and distances

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search Both Directions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler