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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Distance to Target String in a Circular Array

Number: 2598

Difficulty: Easy

Paid? No

Companies: Salesforce, Bloomberg

Problem Description

Given a circular string array "words" and a target string, determine the shortest distance from a specified start index to any occurrence of the target string. Since the array is circular, moving past the last element returns you to the first, and vice versa. If the target doesn't exist in the array, return -1.

Key Insights

  • Treat the array as circular; hence, the distance between two indices i and j can be computed as min(|i - j|, n - |i - j|), where n is the array length.
  • Find all indices where the target appears.
  • If no index contains the target, return -1.
  • Iterate through each occurrence of the target to calculate the minimal movement required from the start index.

Space and Time Complexity

Time Complexity: O(n) - We scan through the entire list once. Space Complexity: O(1) - Only constant extra space is needed.

Solution

We solve the problem by:

  1. Iterating through the "words" array to identify all indices that match the target.
  2. For each matching index, compute the direct distance (absolute difference) and the circular distance (total length minus the direct distance).
  3. Choose the smallest of these distances.
  4. If no match is found, return -1.

This approach ensures that we always capture the minimum number of steps required to reach the target considering both forward and backward movements in the circular array.

Code Solutions

# Define the function to compute the shortest distance
def closet_target(words, target, startIndex):
    n = len(words)
    min_distance = float('inf')
    
    # Iterate over each index in the words array
    for i in range(n):
        if words[i] == target:
            # Calculate the absolute distance from the startIndex
            direct_distance = abs(i - startIndex)
            # For circular array, calculate the circular distance
            circular_distance = n - direct_distance
            # Update the minimum distance found
            min_distance = min(min_distance, direct_distance, circular_distance)
    
    # If no occurrence of target is found, return -1
    return min_distance if min_distance != float('inf') else -1

# Example usage:
result = closet_target(["hello", "i", "am", "leetcode", "hello"], "hello", 1)
print(result)  # Expected output: 1
← Back to All Questions