LeetCode 2515 - Shortest Distance to Target String in a Circular Array

The problem asks us to find the shortest distance from a given starting index in a circular array of strings to a target string.

leetcodeeasyarraystring

LeetCode Problem 2515

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

The problem asks us to find the shortest distance from a given starting index in a circular array of strings to a target string. The circular nature of the array means that moving past the end wraps around to the beginning, and moving before the first element wraps around to the last element. This is important because the shortest distance may involve wrapping around the array in either direction.

The inputs are words, a list of lowercase strings, target, a string we want to reach, and startIndex, the index from which we begin. The output is an integer representing the minimum number of steps needed to reach any occurrence of target. If target does not appear in words, we must return -1.

The constraints indicate that the array length is small (1 <= words.length <= 100) and each string is relatively short (1 <= words[i].length <= 100). This suggests that even O(n²) solutions could be feasible, but simpler O(n) approaches exist and are more elegant.

Key edge cases include:

  • The target is at the starting index.
  • The target appears multiple times, and the shortest path may be left or right.
  • The target does not exist.
  • The array contains only one element.

Approaches

The brute-force approach is to iterate through the array in both directions from the start index and compute the distance to every occurrence of the target. For each element, we calculate the forward distance and the backward distance considering the circular wrap-around. We then take the minimum of these distances. This approach works because it explicitly checks all possible paths, but it requires scanning the array multiple times.

The optimal approach leverages the observation that we can calculate the circular distance between indices using modular arithmetic. For each occurrence of the target, the shortest distance can be expressed as the minimum of moving clockwise or counter-clockwise. By iterating once over the array and applying this calculation, we can determine the minimum distance efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Scan in both directions repeatedly for every target occurrence
Optimal O(n) O(1) Single pass to compute circular distances to all occurrences of target

Algorithm Walkthrough

  1. Initialize a variable min_distance to infinity. This will keep track of the smallest distance found.
  2. Iterate through the array words using an index i.
  3. For each i where words[i] equals target, calculate the forward distance as (i - startIndex + n) % n and the backward distance as (startIndex - i + n) % n.
  4. Update min_distance to be the minimum of itself, the forward distance, and the backward distance.
  5. After iterating through the array, check if min_distance is still infinity. If it is, return -1 since the target was not found. Otherwise, return min_distance.

Why it works: By considering both forward and backward distances for each occurrence of the target and taking the minimum, we guarantee that we find the shortest path in the circular array. The modular arithmetic ensures correct wrap-around calculation.

Python Solution

from typing import List

class Solution:
    def closestTarget(self, words: List[str], target: str, startIndex: int) -> int:
        n = len(words)
        min_distance = float('inf')
        
        for i in range(n):
            if words[i] == target:
                forward = (i - startIndex + n) % n
                backward = (startIndex - i + n) % n
                min_distance = min(min_distance, forward, backward)
        
        return -1 if min_distance == float('inf') else min_distance

The implementation first initializes min_distance as infinity to handle the case where the target is not found. It then iterates through all indices of the array. Whenever it finds the target, it computes both forward and backward circular distances using modular arithmetic. The minimum distance across all occurrences is stored. Finally, if no occurrence was found, it returns -1; otherwise, it returns the computed minimum distance.

Go Solution

func closestTarget(words []string, target string, startIndex int) int {
    n := len(words)
    minDistance := n + 1 // larger than any possible distance
    
    for i, word := range words {
        if word == target {
            forward := (i - startIndex + n) % n
            backward := (startIndex - i + n) % n
            if forward < minDistance {
                minDistance = forward
            }
            if backward < minDistance {
                minDistance = backward
            }
        }
    }
    
    if minDistance > n {
        return -1
    }
    return minDistance
}

The Go implementation follows the same logic. Since Go lacks inf, we initialize minDistance to n+1 as a safe upper bound. Forward and backward distances are computed using modular arithmetic, and the minimum is updated similarly. If no target was found, the function returns -1.

Worked Examples

Example 1: words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1

i words[i] forward backward min_distance
0 hello (0-1+5)%5=4 (1-0+5)%5=1 1
4 hello (4-1+5)%5=3 (1-4+5)%5=2 1

Shortest distance: 1

Example 2: words = ["a","b","leetcode"], target = "leetcode", startIndex = 0

i words[i] forward backward min_distance
2 leetcode (2-0+3)%3=2 (0-2+3)%3=1 1

Shortest distance: 1

Example 3: words = ["i","eat","leetcode"], target = "ate", startIndex = 0

No occurrence found, return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass over the array to check all occurrences of target
Space O(1) Only a few integer variables used, no extra data structures

Since n is at most 100, this solution is very efficient. No extra memory is required beyond simple counters and modular arithmetic.

Test Cases

# Provided examples
assert Solution().closestTarget(["hello","i","am","leetcode","hello"], "hello", 1) == 1
assert Solution().closestTarget(["a","b","leetcode"], "leetcode", 0) == 1
assert Solution().closestTarget(["i","eat","leetcode"], "ate", 0) == -1

# Additional edge cases
assert Solution().closestTarget(["a"], "a", 0) == 0  # target at start
assert Solution().closestTarget(["a","b","a","c"], "c", 2) == 1  # wrapping around
assert Solution().closestTarget(["a","b","c"], "d", 1) == -1  # target missing
assert Solution().closestTarget(["x","y","z","x"], "x", 3) == 0  # target at startIndex
Test Why
Single-element array Ensures start index equals target index returns 0
Multiple occurrences with wrap Validates shortest distance is chosen correctly using circular logic
Missing target Confirms algorithm returns -1 when target does not exist
Target at startIndex Confirms algorithm handles zero-distance case correctly

Edge Cases

One important edge case is when the target is at the start index itself. In this case, both forward and backward distances are zero, and the algorithm correctly returns 0 because min_distance is updated with the minimum of itself and these distances.

Another edge case is when the target appears multiple times. The shortest path might require wrapping around the circular array, and using modular arithmetic ensures that the minimum distance is calculated correctly in both directions.

A third edge case is when the target does not exist in the array. Since min_distance is initialized to infinity (Python) or a value larger than n (Go), the algorithm can safely detect that no occurrence was found and return -1. This avoids accidental false positives in distance calculation.