algoadvance

Leetcode 2515. Shortest Distance to Target String in a Circular Array

Problem Statement

You are given an array of strings words, a target string target, and an integer startIndex. The array is considered to be circular, meaning that the next element of the last element is the first element of the array.

You need to find the shortest distance from startIndex to any occurrence of target. The distance between any two indices i and j is the minimum between the number of steps to go from i to j clockwise and the number of steps to go from i to j counterclockwise.

Return the shortest distance as an integer.

Clarifying Questions

  1. What should be returned if the target string does not exist in the array?
    • The problem does not specify this, so we will assume that the target string is guaranteed to exist in the array.
  2. Are there any constraints on the lengths of the array or on the strings in the array?
    • Typical constraints apply, but they are not explicitly stated. We can assume reasonable limits for a coding interview setting.

Strategy

  1. Identify All Occurrences: Loop through the array words and identify all indices where words[i] equals the target.
  2. Calculate Distances: For each occurrence, compute the distance from the startIndex:
    • Clockwise Distance: Derived by direct iteration from the startIndex.
    • Counterclockwise Distance: Derived by iterating backwards wrapping around the array.
  3. Find Minimum Distance: Out of all calculated distances, return the minimum.

Code

Here’s how we can implement this in Java:

public class Solution {
    public int closetTarget(String[] words, String target, int startIndex) {
        int n = words.length;
        int minDistance = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            if (words[i].equals(target)) {
                int clockwiseDistance = (i - startIndex + n) % n;
                int counterClockwiseDistance = (startIndex - i + n) % n;
                int currentMinDistance = Math.min(clockwiseDistance, counterClockwiseDistance);
                minDistance = Math.min(minDistance, currentMinDistance);
            }
        }

        return minDistance;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] words = {"hello", "world", "leetcode", "hello"};
        String target = "hello";
        int startIndex = 1;
        System.out.println(solution.closetTarget(words, target, startIndex)); // Output: 1
    }
}

Time Complexity

The time complexity of the above solution is (O(n)), where (n) is the number of elements in the array words:

This ensures we get the shortest distance efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI