Shortest Distance to Target String in a Circular Array — Easy Problem & Solution

Problem statement

The array words is circular: stepping right from the last index lands on index 0, and stepping left from index 0 lands on the last.

Starting at startIndex, return the minimum number of steps needed to reach any index holding target, or -1 if target does not appear.

Example 1

Input: words = ["kata","duel","codekairo","rank","codekairo"], target = "codekairo", startIndex = 1
Output: 1
Explanation: One step right reaches index 2.

Example 2

Input: words = ["a","b","codekairo"], target = "codekairo", startIndex = 0
Output: 1
Explanation: One step left wraps to index 2.

Example 3

Input: words = ["i","eat","kata"], target = "ate", startIndex = 0
Output: -1

Constraints

• 1 <= words.length <= 100
• 1 <= words[i].length, target.length <= 10
• 0 <= startIndex < words.length
• Strings consist of lowercase English letters.

How to solve Shortest Distance to Target String in a Circular Array

The circle gives two routes to any index, and their lengths are the two modular differences. Scanning every match and taking the smaller route is enough.

Approach

1. Sweep the array for indices holding target.
2. For each, compute the clockwise distance (i - startIndex + n) % n and the anticlockwise one (startIndex - i + n) % n.
3. Keep the minimum of all those values, or -1 if no match was found.

Why it works

On a cycle of length n, the two routes between two positions sum to n (or are both 0 when the positions coincide), so the shorter of the two modular differences is the graph distance.

Complexity

• Time — O(n · L)
• Space — O(1)

Pitfalls

• Computing |i - startIndex| ignores the wrap and overstates distances near the ends.
• Adding n before the modulo is what keeps the result non-negative in languages where % can go negative.
• startIndex itself may hold the target, giving a distance of 0.

Reference solution

Python

from typing import List

def closetTarget(words: List[str], target: str, startIndex: int) -> int:
    n = len(words)
    best = -1
    for i, w in enumerate(words):
        if w != target:
            continue
        d = min((i - startIndex) % n, (startIndex - i) % n)
        if best < 0 or d < best:
            best = d
    return best

JavaScript

var closetTarget = function(words, target, startIndex) {
    var n = words.length, best = -1;
    for (var i = 0; i < n; i++) {
        if (words[i] !== target) continue;
        var forward = (i - startIndex + n) % n;
        var backward = (startIndex - i + n) % n;
        var d = Math.min(forward, backward);
        if (best < 0 || d < best) best = d;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy