3488. Closest Equal Element Queries

Description

You are given a circular array nums and an array queries.

For each query i, you have to find the following:

• The minimum distance between the element at index queries[i] and any other index j in the circular array, where nums[j] == nums[queries[i]]. If no such index exists, the answer for that query should be -1.

Return an array answer of the same size as queries, where answer[i] represents the result for query i.

 

Example 1:

Input: nums = [1,3,1,4,1,3,2], queries = [0,3,5]

Output: [2,-1,3]

Explanation:

• Query 0: The element at queries[0] = 0 is nums[0] = 1. The nearest index with the same value is 2, and the distance between them is 2.
• Query 1: The element at queries[1] = 3 is nums[3] = 4. No other index contains 4, so the result is -1.
• Query 2: The element at queries[2] = 5 is nums[5] = 3. The nearest index with the same value is 1, and the distance between them is 3 (following the circular path: 5 -> 6 -> 0 -> 1).

Example 2:

Input: nums = [1,2,3,4], queries = [0,1,2,3]

Output: [-1,-1,-1,-1]

Explanation:

Each value in nums is unique, so no index shares the same value as the queried element. This results in -1 for all queries.

 

Constraints:

• 1 <= queries.length <= nums.length <= 105
• 1 <= nums[i] <= 106
• 0 <= queries[i] < nums.length

 

Solutions

Solution: Binary Search + Hash Table

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number[]} queries
 * @return {number[]}
 */
const solveQueries = function (nums, queries) {
  const n = nums.length;
  const numToIndexMap = new Map();

  for (let index = 0; index < n; index++) {
    const num = nums[index];

    if (!numToIndexMap.has(num)) {
      numToIndexMap.set(num, []);
    }

    numToIndexMap.get(num).push(index);
  }

  const findNearestDistance = (target, indices) => {
    const m = indices.length;
    let left = 0;
    let right = m - 1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);

      if (indices[mid] > target) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }

    const prev = (right - 1 + m) % m;
    const next = (right + 1) % m;
    const prevDis = Math.abs(indices[right] - indices[prev]);
    const nextDis = Math.abs(indices[next] - indices[right]);

    return Math.min(prevDis, n - prevDis, nextDis, n - nextDis);
  };

  return queries.map(index => {
    const indices = numToIndexMap.get(nums[index]);

    if (indices.length === 1) return -1;

    return findNearestDistance(index, indices);
  });
};