algoadvance

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

Problem Statement

You are given an array of strings words and a string target. You need to determine the shortest distance between two identical occurrences of the target string in a circular array.

A circular array means that after the last element, the array resumes from the first element again, forming a loop. If the target string appears only once or not at all, return -1.

Clarifying Questions

1. Input Constraints:
   • How long can the words array be?
   • Are there any constraints on the length of the strings within the words array?
2. Edge Cases:
   • What should we return if target is not present in the array?
   • How should we handle the case where target occurs exactly once?
3. Data Type:
   • Can words contain special characters or is it limited to alphanumeric characters?

Strategy

1. Tracking Indices:
   • First, traverse the array to find all indices where the target string appears.
2. Calculate Distances:
   • If the target appears fewer than twice, return -1.
   • Compute the smallest distance between consecutive appearances considering the circular nature of the array.
3. Circular Array Handling:
   • Add an extra distance computation for wrapping around from the end of the array to the beginning.

Code

#include <vector>
#include <string>
#include <algorithm>
#include <climits> // For INT_MAX

int shortestDistanceToTargetString(const std::vector<std::string>& words, const std::string& target) {
    std::vector<int> targetIndices;

    // Collect indices of the target string's occurrences
    for (int i = 0; i < words.size(); ++i) {
        if (words[i] == target) {
            targetIndices.push_back(i);
        }
    }

    // If target appears less than 2 times, return -1
    if (targetIndices.size() < 2) {
        return -1;
    }

    int minDistance = INT_MAX;
    int n = words.size();
    
    // Compute the minimum distance between consecutive indices
    for (size_t i = 1; i < targetIndices.size(); ++i) {
        int distance = (targetIndices[i] - targetIndices[i-1] + n) % n;
        minDistance = std::min(minDistance, distance);
    }

    // Wrap around: Consider distance from last occurrence back to the first occurrence
    int wrapAroundDistance = (targetIndices[0] + n - targetIndices.back()) % n;
    minDistance = std::min(minDistance, wrapAroundDistance);

    return minDistance;
}

Time Complexity

• Time Complexity: O(n)
  • Collecting indices requires traversing the words array once — O(n).
  • Calculating distances is linear in the number of occurrences of target — let’s denote this number as k. Thus O(k), but since k <= n, this part is effectively O(n) in the worst case.
• Space Complexity: O(k)
  • We store indices of the target in a vector, where k is the number of occurrences. In the worst case, k can be n, making space complexity O(n).

This algorithm provides an efficient solution to determine the shortest distance in a circular arrangement for given scenarios.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?