Shortest Distance to Target String in a Circular Array

Easy

#2295Time: O(N * L), where `N` is the length of the `words` array and `L` is the maximum length of a string in the array. We iterate through all `N` words, and for each word, the string comparison `equals()` takes O(L) time in the worst case.Space: O(1), as we only use a constant amount of extra space for variables like `minDist` and the loop counter.

Data structures

Array String

Prompt

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.

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:

words

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] and target consist of only lowercase English letters.
0 <= startIndex < words.length

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a straightforward linear scan of the entire words array. For every element that matches the target string, we calculate its shortest circular distance from the startIndex. We maintain a variable to keep track of the minimum distance found so far across all matches.

Algorithm

Initialize a variable minDist to a very large number (e.g., Integer.MAX_VALUE).
Iterate through the words array with an index i from 0 to n-1, where n is the length of the array.
Inside the loop, if words[i] equals the target string:
- Calculate the direct distance: dist = abs(i - startIndex).
- Calculate the circular distance: circularDist = n - dist.
- The shortest distance to this occurrence is min(dist, circularDist).
- Update minDist by taking the minimum of its current value and this new shortest distance.
After the loop, if minDist remains at its initial large value, the target was not found, so return -1. Otherwise, return minDist.

Walkthrough

The core idea is to find all occurrences of the target string and then determine which one is closest to the startIndex. We can achieve this with a single pass through the array.

We initialize a variable, minDist, to the maximum possible integer value to act as a placeholder for the minimum distance. Then, we loop through each word in the words array from index 0 to n-1.

For each word, we check if it matches the target. If it does, we calculate the shortest distance from startIndex to the current index i. In a circular array of length n, the distance between two indices a and b is the minimum of the clockwise distance abs(a - b) and the counter-clockwise distance n - abs(a - b). We update minDist with this value if it's smaller than the current minDist.

After checking all the words, if minDist is still at its initial maximum value, it implies the target was never found, and we should return -1. Otherwise, minDist holds the shortest distance to a target string, which we return.

1class Solution {2    public int closetTarget(String[] words, String target, int startIndex) {3        int n = words.length;4        int minDist = Integer.MAX_VALUE;5 6        for (int i = 0; i < n; i++) {7            if (words[i].equals(target)) {8                int dist = Math.abs(i - startIndex);9                int circularDist = Math.min(dist, n - dist);10                minDist = Math.min(minDist, circularDist);11            }12        }13 14        return (minDist == Integer.MAX_VALUE) ? -1 : minDist;15    }16}

Complexity

Time

O(N * L), where `N` is the length of the `words` array and `L` is the maximum length of a string in the array. We iterate through all `N` words, and for each word, the string comparison `equals()` takes O(L) time in the worst case.

Space

O(1), as we only use a constant amount of extra space for variables like `minDist` and the loop counter.

Trade-offs

Pros

The logic is simple to understand and implement.
It correctly finds the shortest distance by exhaustively checking all possibilities.

Cons

This approach is less efficient as it always iterates through the entire array, regardless of how close the target is to the startIndex.

A more optimized approach is to perform a bidirectional search starting from the startIndex. Instead of scanning the entire array, we expand our search outwards from the starting point, one step at a time in both the left and right directions. The first time we encounter the target string, we are guaranteed to have found it via the shortest possible path.

Algorithm

Get the length of the array, n.
Loop with a distance variable d from 0 up to n / 2.
In each iteration, check two positions: d steps to the right and d steps to the left of startIndex.
Calculate the right index: rightIdx = (startIndex + d) % n.
If words[rightIdx] matches the target, return d because this is the shortest distance.
Calculate the left index: leftIdx = (startIndex - d + n) % n.
If words[leftIdx] matches the target, return d.
If the loop completes without finding the target, it means the target is not in the array, so return -1.

Walkthrough

This method simulates the process of moving away from startIndex one step at a time, simultaneously to the right and to the left. We use a loop that iterates through possible distances, from 0 upwards.

The maximum possible shortest distance in a circular array of size n is n / 2. Therefore, we only need to check distances from 0 to n / 2.

For each distance d, we calculate the corresponding indices: (startIndex + d) % n for the rightward move and (startIndex - d + n) % n for the leftward move. The + n in the leftward calculation handles potential negative results from the subtraction, ensuring the index remains valid.

We check if the word at either of these two indices matches the target. If a match is found, we can immediately return the current distance d, as our incremental search guarantees this is the shortest path. If the loop finishes without finding any match, it means the target is not present in the array, and we return -1.

1class Solution {2    public int closetTarget(String[] words, String target, int startIndex) {3        int n = words.length;4        for (int dist = 0; dist <= n / 2; dist++) {5            // Check `dist` steps to the right6            int rightIndex = (startIndex + dist) % n;7            if (words[rightIndex].equals(target)) {8                return dist;9            }10            11            // Check `dist` steps to the left12            int leftIndex = (startIndex - dist + n) % n;13            if (words[leftIndex].equals(target)) {14                return dist;15            }16        }17        18        return -1;19    }20}

Complexity

Time

O(N * L) in the worst case, where `N` is the number of words and `L` is the maximum string length. The worst case occurs when the target is not found or is located at the maximum possible distance (`n/2`), requiring us to check all `n` elements. However, its average-case performance is better than the single-pass approach.

Space

O(1), as it uses only a few variables to keep track of indices and distance, requiring constant extra space.

Trade-offs

Pros

More efficient on average, as it can terminate early.
If the target is at or near the startIndex, the solution is found very quickly.
The logic directly models the problem of finding the 'closest' item.

Cons

The worst-case time complexity is the same as the brute-force approach, although it performs better on average.

Solutions

Solution

1class Solution {2public3  int closetTarget(String[] words, String target, int startIndex) {4    int n = words.length;5    int ans = n;6    for (int i = 0; i < n; ++i) {7      String w = words[i];8      if (w.equals(target)) {9        int t = Math.abs(i - startIndex);10        ans = Math.min(ans, Math.min(t, n - t));11      }12    }13    return ans == n ? -1 : ans;14  }15}

1class Solution {2public:3  int closetTarget(vector<string> &words, string target, int startIndex) {4    int n = words.size();5    int ans = n;6    for (int i = 0; i < n; ++i) {7      auto w = words[i];8      if (w == target) {9        int t = abs(i - startIndex);10        ans = min(ans, min(t, n - t));11      }12    }13    return ans == n ? -1 : ans;14  }15};

1class Solution:2    def closetTarget(self, words: List[str], target: str, startIndex: int) -> int: n = len(words) ans = n for i, w in enumerate(words): if w == target: t = abs(i - startIndex) ans = min(ans, t, n - t) return - 1 if ans == n else ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem