2515. Shortest Distance to Target String in a Circular Array

EasyArrayString
Leetcode Link

Problem Description

In this problem, we are given a list of strings called words that is arranged in a circular fashion. What this means is that if you were to look at the array of words, the word that comes after the last one is the first word of the list, creating a loop-like structure.

We are also given a target string that we need to find in the words list, starting the search from a given startIndex. The goal is to figure out the shortest distance from this starting index to the index where the target string is located.

The search can proceed in either direction - moving to the next word in the list or to the previous one. When searching, each step taken counts as 1, regardless of the direction.

To summarize:

  • If the target string is present, we need to find and return the minimum number of steps required to reach it from the startIndex.
  • If the target string is not in the list, we should return -1.

Keep in mind that the next element of words[i] is words[(i + 1) % n] and the previous element is words[(i - 1 + n) % n], where n is the total number of elements in words, effectively making it a circular array.

Intuition

To solve this problem, the intuition is to iterate through the entire circular list to locate the target string. As we encounter the given target, we calculate how far it is from our startIndex.

We consider two scenarios to find the shortest path:

  1. Moving clockwise (forward) to reach the target.
  2. Moving counter-clockwise (backward) to reach the target.

Let's consider an example where we have a list of 6 words and our startIndex is at position 1. If our target is at position 4, we can reach it in 3 steps by moving forward or in 3 steps by moving backward (since the array is circular). We always want the shortest number of steps.

The python code defines a function called closetTarget that calculates the minimum number of steps required to reach the target word from the startIndex. The distance is calculated in both directions for each occurrence of the target and the minimum is stored. After checking all the words, the function returns the smallest distance found. If the target word is absent, the function will return -1.

The key to this approach is realizing that the minimum distance to reach the target from the current index is either directly (forward or backward) or going the entire circle minus the direct distance, which effectively means going in the opposite direction.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following shows the order of node visit in a Breadth-first Search?

Solution Approach

The implementation leverages a simple linear search along with modular arithmetic to handle the circular nature of the array.

The algorithm proceeds as follows:

  1. We initialize a variable ans to n, which is the length of the words list. This initial value acts as a placeholder for the scenario where the target is not found.

  2. We then loop over the words list using enumerate to get both the index i and the word w at each iteration.

  3. For every word w that matches the target, we calculate the distance t from startIndex in two ways:

    • Direct distance: t = abs(i - startIndex)
    • Circular distance: n - t, which represents the distance if we were to go around the array in the opposite direction.

  4. We update ans with the minimum of its current value, the direct distance t, and the circular distance n - t. This ensures that after scanning all words, ans holds the shortest distance required to reach target from startIndex.

  5. If we finish the loop and ans remains equal to n, it means that the target word was not found in the words list. In this case, we return -1.

  6. Otherwise, we return the value stored in ans, which is the shortest distance found.

An important detail to note is the use of modular arithmetic to deal with the circular indexing, but since we are using Python's abs function to calculate the direct distance, we do not explicitly use the modulus operator % in our distance calculations. Instead, the modulus operator would be necessary if we were manually wrapping around the indices.

This algorithm will work efficiently as it only requires a single pass over the list, giving it a time complexity of O(n), where n is the number of words in the list. We don't use any additional data structures, giving us a space complexity of O(1).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Example Walkthrough

Consider the following example to illustrate the solution approach:

  • Let's assume words = ["apple", "banana", "cherry", "date", "elderberry", "fig"] is our list of words arranged in a circular fashion.
  • The target string that we are looking for is "date".
  • Our startIndex is 2, which means we start our search from the word "cherry".

Following the steps outlined in the solution approach:

  1. We set ans = 6 as there are 6 words in our list. This is our initial best-case scenario value, which we will update if we find the word.

  2. We enumerate through our list to get each word and its index:

    • Index 0, Word "apple": Not our target.
    • Index 1, Word "banana": Not our target.
    • Index 2, Word "cherry": This is our starting index.
    • Index 3, Word "date": This is our target!

  3. Since we have found our target at index 3, we calculate the direct distance from our startIndex (2) to our target index (3):

    • Direct distance: t = abs(3 - 2) = 1

    We also calculate the circular distance by subtracting this direct distance from the total number of words (n):

    • Circular distance: n - t = 6 - 1 = 5

  4. We update ans with the minimum of its current value (6), the direct distance (1), and the circular distance (5). This update gives us ans = min(6, 1, 5) = 1.

  5. Since we successfully found the word, we don't need to return -1, and we can skip to step 6.

  6. We return the value stored in ans, which is 1, indicating that the target word "date" is 1 step away from the starting index 2 (the word "cherry") in the list.

Thus, the function closetTarget will return 1 for this example, because the shortest path to the target "date" from startIndex 2 is by moving forward one step in the circular array.

Solution Implementation

1from typing import List
2
3class Solution:
4    def closestTarget(self, words: List[str], target: str, start_index: int) -> int:
5        # The length of the list of words.
6        num_words = len(words)
7        # Initialize the minimum distance with the number of words,
8        # which is an upper bound on the distance we can find.
9        min_distance = num_words
10      
11        # Iterate through each word in the list along with their index.
12        for index, word in enumerate(words):
13            # Check if the current word is the target we're searching for.
14            if word == target:
15                # Calculate the absolute distance from the current word to the start index.
16                distance = abs(index - start_index)
17                # The minimum distance is updated with the smallest of the current minimum,
18                # the new distance, or the circular distance (num_words - distance).
19                min_distance = min(min_distance, distance)
20      
21        # If min_distance is still num_words, it means the target was not found.
22        # Hence, return -1. Otherwise, return the found minimum distance.
23        return -1 if min_distance == num_words else min_distance
24
1class Solution {
2    public int closestTarget(String[] words, String target, int startIndex) {
3        // Get the length of the words array.
4        int n = words.length;
5        // Initialize the answer with the maximum possible distance which is n.
6        int closestDistance = n;
7      
8        // Iterate through the words array to find the closest target.
9        for (int i = 0; i < n; ++i) {
10            // Current word at index i.
11            String currentWord = words[i];
12            // Check if the current word matches the target word.
13            if (currentWord.equals(target)) {
14                // Calculate the direct distance from the start index to the current index.
15                int directDistance = Math.abs(i - startIndex);
16                // Calculate the distance assuming we can wrap around the array.
17                int wrappedDistance = n - directDistance;
18                // Choose the smaller of the two distances to find the closest position.
19                closestDistance = Math.min(closestDistance, Math.min(directDistance, wrappedDistance));
20            }
21        }
22        // If the closestDistance is still n, that means the target was not found.
23        // In that case, return -1. Otherwise, return the closest distance found.
24        return closestDistance == n ? -1 : closestDistance;
25    }
26}
27
1#include <vector>
2#include <string>
3#include <cmath> // For abs() function
4#include <algorithm> // For min() function
5
6class Solution {
7public:
8    // Function to find the closest index of a target string from the given startIndex
9    // within an array of words.
10    // Parameters:
11    // - words: A vector of strings representing the array of words.
12    // - target: The string target we are trying to find the closest index to.
13    // - startIndex: The index from which we start searching for the closest occurrence.
14    // Returns: The minimum distance to the closest occurrence of the target word. If not found, returns -1.
15    int closestTarget(vector<string>& words, string target, int startIndex) {
16        int n = words.size(); // The number of words in the vector
17        int minDistance = n; // Initialize the minimum distance with the maximum possible value, the size of the words vector
18
19        // Iterate over the vector to find the occurrences of the target string
20        for (int i = 0; i < n; ++i) {
21            // If the current word matches the target word
22            if (words[i] == target) {
23                // Calculate the distance from the startIndex to the current index
24                int currentDistance = abs(i - startIndex);
25                // Find the minimum distance considering the circular array (wrapping around)
26                minDistance = min(minDistance, min(currentDistance, n - currentDistance));
27            }
28        }
29
30        // If minDistance is unchanged, the target was not found; return -1.
31        // Otherwise, return the minimum distance to the nearest target word.
32        return minDistance == n ? -1 : minDistance;
33    }
34};
35
1// Finds index of the closet 'target' string in 'words' array from a specified 'startIndex'.
2function closetTarget(words: string[], target: string, startIndex: number): number {
3    const wordsCount = words.length; // Total number of words in the array
4  
5    // Loop through the words array until the mid-point
6    for (let offset = 0; offset <= wordsCount >> 1; offset++) {
7        // Calculate the index to the left of the start index, wrapping if necessary
8        const leftIndex = (startIndex - offset + wordsCount) % wordsCount;
9        if (words[leftIndex] === target) {
10            return offset; // Return the offset if target is found 
11        }
12      
13        // Calculate the index to the right of the start index, wrapping if necessary
14        const rightIndex = (startIndex + offset) % wordsCount;
15        if (words[rightIndex] === target) {
16            return offset; // Return the offset if target is found
17        }
18    }
19    // Return -1 if the target is not found
20    return -1;
21}
22
Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(n), where n is the number of words in the input list words. This is because there is a single loop that iterates over each word in the list exactly once to check if it matches the target.

Space Complexity

The space complexity of the provided code is O(1) regardless of the size of the input. This is because the code only uses a few extra variables (n, ans, i, w, t) that do not depend on the size of the input list words.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫