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 1: Circular Array + Hash Table

According to the problem description, we need to find the minimum distance between each element in the array and its previous identical element, as well as the minimum distance to its next identical element. Since the array is circular, we need to consider the circular nature of the array. We can extend the array to twice its original length, and then use hash tables \(\textit{left}\) and \(\textit{right}\) to record the positions where each element last appeared and will next appear, respectively. We calculate the minimum distance between each position's element and another identical element, recording it in the array \(\textit{d}\). Finally, we traverse the queries, and for each query \(i\), we take the minimum value of \(\textit{d}[i]\) and \(\textit{d}[i+n]\). If this value is greater than or equal to \(n\), it means there is no element identical to the queried element, so we return \(-1\); otherwise, we return the value.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the array \(\textit{nums}\).

Python3JavaC++GoTypeScript

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        m = n << 1
        d = [m] * m
        left = {}
        for i in range(m):
            x = nums[i % n]
            if x in left:
                d[i] = min(d[i], i - left[x])
            left[x] = i
        right = {}
        for i in range(m - 1, -1, -1):
            x = nums[i % n]
            if x in right:
                d[i] = min(d[i], right[x] - i)
            right[x] = i
        for i in range(n):
            d[i] = min(d[i], d[i + n])
        return [-1 if d[i] >= n else d[i] for i in queries]

class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        int n = nums.length;
        int m = n * 2;
        int[] d = new int[m];
        Arrays.fill(d, m);

        Map<Integer, Integer> left = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int x = nums[i % n];
            if (left.containsKey(x)) {
                d[i] = Math.min(d[i], i - left.get(x));
            }
            left.put(x, i);
        }

        Map<Integer, Integer> right = new HashMap<>();
        for (int i = m - 1; i >= 0; i--) {
            int x = nums[i % n];
            if (right.containsKey(x)) {
                d[i] = Math.min(d[i], right.get(x) - i);
            }
            right.put(x, i);
        }

        for (int i = 0; i < n; i++) {
            d[i] = Math.min(d[i], d[i + n]);
        }

        List<Integer> ans = new ArrayList<>();
        for (int query : queries) {
            ans.add(d[query] >= n ? -1 : d[query]);
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
        int n = nums.size();
        int m = n * 2;
        vector<int> d(m, m);

        unordered_map<int, int> left;
        for (int i = 0; i < m; i++) {
            int x = nums[i % n];
            if (left.count(x)) {
                d[i] = min(d[i], i - left[x]);
            }
            left[x] = i;
        }

        unordered_map<int, int> right;
        for (int i = m - 1; i >= 0; i--) {
            int x = nums[i % n];
            if (right.count(x)) {
                d[i] = min(d[i], right[x] - i);
            }
            right[x] = i;
        }

        for (int i = 0; i < n; i++) {
            d[i] = min(d[i], d[i + n]);
        }

        vector<int> ans;
        for (int query : queries) {
            ans.push_back(d[query] >= n ? -1 : d[query]);
        }
        return ans;
    }
};

func solveQueries(nums []int, queries []int) []int {
    n := len(nums)
    m := n * 2
    d := make([]int, m)
    for i := range d {
        d[i] = m
    }

    left := make(map[int]int)
    for i := 0; i < m; i++ {
        x := nums[i%n]
        if idx, exists := left[x]; exists {
            d[i] = min(d[i], i-idx)
        }
        left[x] = i
    }

    right := make(map[int]int)
    for i := m - 1; i >= 0; i-- {
        x := nums[i%n]
        if idx, exists := right[x]; exists {
            d[i] = min(d[i], idx-i)
        }
        right[x] = i
    }

    for i := 0; i < n; i++ {
        d[i] = min(d[i], d[i+n])
    }

    ans := make([]int, len(queries))
    for i, query := range queries {
        if d[query] >= n {
            ans[i] = -1
        } else {
            ans[i] = d[query]
        }
    }
    return ans
}

function solveQueries(nums: number[], queries: number[]): number[] {
    const n = nums.length;
    const m = n * 2;
    const d: number[] = Array(m).fill(m);

    const left = new Map<number, number>();
    for (let i = 0; i < m; i++) {
        const x = nums[i % n];
        if (left.has(x)) {
            d[i] = Math.min(d[i], i - left.get(x)!);
        }
        left.set(x, i);
    }

    const right = new Map<number, number>();
    for (let i = m - 1; i >= 0; i--) {
        const x = nums[i % n];
        if (right.has(x)) {
            d[i] = Math.min(d[i], right.get(x)! - i);
        }
        right.set(x, i);
    }

    for (let i = 0; i < n; i++) {
        d[i] = Math.min(d[i], d[i + n]);
    }

    return queries.map(query => (d[query] >= n ? -1 : d[query]));
}

Comments