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 indexjin the circular array, wherenums[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] = 0isnums[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] = 3isnums[3] = 4. No other index contains 4, so the result is -1. - Query 2: The element at
queries[2] = 5isnums[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 <= 1051 <= nums[i] <= 1060 <= queries[i] < nums.length
Solutions
This optimized version takes a streamlined approach by handling the first occurrence of a value separately (directly initializing the Map entry instead of adding it to an empty array), then for subsequent occurrences it updates only the first and last elements' distances and immediately calculates the new entry's distance once (rather than updating it later). This reduces unnecessary distance recalculations compared to earlier solutions—particularly avoiding the second-to-last element tracking—while maintaining the same overall O(n) preprocessing and O(1) query performance.
/**
* @param {number[]} nums
* @param {number[]} queries
* @return {number[]}
*/
var solveQueries = function(nums, queries) {
const n = nums.length;
const map = new Map();
for (let i = 0; i < n; i++) {
const arr = map.get(nums[i]);
if (!arr) {
map.set(nums[i], [[i, Infinity]]);
continue;
}
const first = arr[0];
const last = arr[arr.length - 1];
const diff1 = i - first[0];
const diff2 = i - last[0];
first[1] = Math.min(first[1], diff1, n - diff1);
last[1] = Math.min(last[1], diff2, n - diff2);
arr.push([i, Math.min(diff2, n - diff1)]);
}
const tempArr = [];
for (let i = n - 1; i >= 0; i--) {
const arr = map.get(nums[i]).pop();
tempArr.push(arr[1]);
}
tempArr.reverse();
return queries.map(query => tempArr[query] === Infinity ? -1 : tempArr[query]);
};