Skip to content

3488. Closest Equal Element Queries 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
    const int n = nums.size();
    vector<int> ans;
    // minDist[i] := the minimum distance between nums[i], and any other index j
    // in the circular array, where nums[j] == nums[i]
    vector<int> minDist(n, n);
    unordered_map<int, int> lastSeen;

    for (int i = 0; i < n * 2; ++i) {
      const int index = i % n;
      const int num = nums[index];
      if (const auto it = lastSeen.find(num); it != lastSeen.cend()) {
        const int prevIndex = it->second % n;
        const int d = i - prevIndex;
        minDist[index] = min(minDist[index], d);
        minDist[prevIndex] = min(minDist[prevIndex], d);
      }
      lastSeen[num] = i;
    }

    for (const int query : queries)
      ans.push_back(minDist[query] == n ? -1 : minDist[query]);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public List<Integer> solveQueries(int[] nums, int[] queries) {
    final int n = nums.length;
    List<Integer> ans = new ArrayList<>();
    // minDist[i] := the minimum distance between nums[i], and any other index j in the circular
    // array, where nums[j] == nums[i]
    int[] minDist = new int[n];
    Arrays.fill(minDist, n);
    Map<Integer, Integer> lastSeen = new HashMap<>();

    for (int i = 0; i < n * 2; ++i) {
      final int index = i % n;
      final int num = nums[index];
      if (lastSeen.containsKey(num)) {
        final int prevIndex = lastSeen.get(num) % n;
        final int d = i - prevIndex;
        minDist[index] = Math.min(minDist[index], d);
        minDist[prevIndex] = Math.min(minDist[prevIndex], d);
      }
      lastSeen.put(num, i);
    }

    for (final int query : queries)
      ans.add(minDist[query] == n ? -1 : minDist[query]);

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def solveQueries(self, nums: list[int], queries: list[int]) -> list[int]:
    n = len(nums)
    # minDist[i] := the minimum distance between nums[i], and any other index j
    # in the circular array, where nums[j] == nums[i]
    minDist = [n] * n
    lastSeen = {}

    for i in range(n * 2):
      index = i % n
      num = nums[index]
      if num in lastSeen:
        prevIndex = lastSeen[num] % n
        d = i - prevIndex
        minDist[index] = min(minDist[index], d)
        minDist[prevIndex] = min(minDist[prevIndex], d)
      lastSeen[num] = i

    return [-1 if minDist[query] == n
            else minDist[query]
            for query in queries]