We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Distance to Target String in a Circular Array

Difficulty: Easy

Problem Description

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. 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.

Key Insights

  • The array is circular, meaning the end connects back to the start.
  • We can move left or right to find the target.
  • We need to calculate distances in both directions and choose the minimum.
  • If the target is not found in the array, return -1.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of elements in the words array, since we might need to scan the entire array to find the target. Space Complexity: O(1) - we use constant space for distance calculations.

Solution

To solve the problem, we can use a simple linear search to find all the indices of the target in the words array. For each index where the target is found, we compute the distance from startIndex both in the clockwise direction and counterclockwise direction. The minimum of these distances will be our answer. If the target is not found at all, we return -1.

Code Solutions

def shortestDistance(words, target, startIndex):
    n = len(words)
    target_indices = [i for i, word in enumerate(words) if word == target]
    
    if not target_indices:
        return -1
    
    min_distance = float('inf')
    
    for idx in target_indices:
        # Calculate clockwise distance
        clockwise_distance = (idx - startIndex) % n
        # Calculate counterclockwise distance
        counterclockwise_distance = (startIndex - idx) % n
        # Update minimum distance
        min_distance = min(min_distance, clockwise_distance, counterclockwise_distance)
    
    return min_distance
← Back to All Questions