Minimum distance to target value from each index in given Array – GeeksforGeeks

Given an array of words[] that is arranged in a circular manner and a target string that needs to be found. The circular arrangement means that the array’s end is connected to the beginning of the array. To move from one word to another, you can either move to the next or the previous word from the current word in one step at a time, the task is to find the shortest distance required to reach the target string starting from the ‘startIndex’ in the circular array. If the target string is not present in the ‘words’ array, return -1.

Examples:

Input: words = [“hello”, “i”, “am”, “GeekGorGeek”, “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.

Input: words = [“i”, “love”, “GFG”], target = “eat”, startIndex = 0
Output: -1
Explanation: Since “eat” does not exist in words, we return -1.

Approach: To solve the problem follow the below idea:

The first search moves to the right of the startIndex, while the second search moves to the left. The distances between the target and the startIndex are calculated for both searches, and the minimum distance is returned as the result. If the target is not found within the array, the method returns -1.

Below is the implementation for the above approach:

• The function takes in three parameters: words, a vector of strings; target, a string; and startIndex, an integer.
• The first line of the function assigns the size of the words vector to the variable n.
• The variable rightDistance is initialized to 0. This variable will be used to keep track of how many words to the right of the startIndex position have been checked before finding the target.
• The function enters a for-loop that will continue indefinitely (since true is used as the loop condition).
• Inside the for-loop, the function first checks if rightDistance is equal to n. If it is, it means that the entire vector has been searched without finding the target, so the function returns -1 to indicate that the target was not found.
• If rightDistance is not equal to n, the function checks if the word at the current position, words[i], is equal to the target. If it is, the function breaks out of the loop.
• If words[i] is not equal to the target, the function increments rightDistance and moves to the next position to the right using the formula (i+1) % n.
• After the loop breaks, the function initializes leftDistance to 0. This variable will be used to keep track of how many words to the left of the startIndex position have been checked before finding the target.
• The function enters a second for-loop that is identical to the first one, except that it searches for the target by moving to the left using the formula (i-1+n) % n.
• Once the second for-loop breaks, the function checks if rightDistance is less than or equal to leftDistance. If it is, the function returns rightDistance, which represents the distance between the startIndex position and the closest occurrence of the target to the right. 
• If leftDistance is less than rightDistance, the function returns leftDistance, which represents the distance between the startIndex position and the closest occurrence of the target to the left

Below is the implementation for the above approach:

Time Complexity:  O(n), where n is the length of the input array of “words”.
Auxiliary Space: O(1)