Shortest Distance to Target String in a Circular Array

Easy
754.

Shortest Distance to Target String in a Circular Array

Shortest Distance to Target String in a Circular Array is an easy coding problem on arrays, strings and two pointers, asked in Amazon, TCS and Capgemini interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @param {string} target
 * @param {number} startIndex
 * @return {number}
 */
var closetTarget = function(words, target, startIndex) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Shortest Distance to Target String in a Circular Array Solution

Shortest Distance to Target String in a Circular Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Shortest Distance to Target String in a Circular Array is an easy coding problem on arrays, strings and two pointers, asked in Amazon, TCS and Capgemini interviews.

  • Difficulty: Easy
  • Topics: Arrays, Strings, Two Pointers
  • Asked at: Amazon, TCS, Capgemini
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Shortest Distance to Target String in a Circular Array

  1. Hint 1

    For each matching index, the distance is the smaller of going right and going left.

  2. Hint 2

    Going right takes (i - startIndex + n) % n steps; going left takes (startIndex - i + n) % n.

  3. Hint 3

    Take the minimum over all matches, or return -1 if there are none.

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

Java

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

C++

int closetTarget(vector<string>& words, string target, int startIndex) {
    int n = (int) words.size(), best = -1;
    for (int i = 0; i < n; i++) {
        if (words[i] != target) continue;
        int forward = (i - startIndex + n) % n;
        int backward = (startIndex - i + n) % n;
        int d = min(forward, backward);
        if (best < 0 || 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings