3488. Closest Equal Element Queries

Problem Statement

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.

Input

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 <= 10^5
1 <= nums[i] <= 10^6
0 <= queries[i] < nums.length

Intuition

We can track the index of each element in a hashmap. Then the idea is just to use the stored indices of each component, compare the previous and next index, and only consider the minimum. We can make use of binary search in the List of indices that we store for efficiency.

Approach

• Traverse the array and store index in a hashmap.
• Traverse through the query and for each query, see how many elements in the hashmap is stored by checking size.
• If size is 1, then no more repeating elements, return -1.
• Else, we need to consider previous and next elements keeping cases to consider if the index we are working on is at the start of the index list or end of index list in the hashmap.
• Binary search to find where our query index is inside the hashmap list of index.

Complexity

Time complexity:

O(length of array) + O(length of query * log(size of hashmap indices list))

Space complexity:

O(N) for storing the indices list.

Code

class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        int numsLength = nums.length;
        int queriesLength = queries.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < numsLength; i++) {
            int num = nums[i];
            if (!map.containsKey(num)) {
                map.put(num, new ArrayList<>());
                map.get(num).add(i);
            }
            else {
                map.get(num).add(i);
            }
        }
        int index = 0;
        List<Integer> result = new ArrayList<>();
        for (int query : queries) {
            List<Integer> indices = map.get(nums[query]);
            //System.out.println(indices);
            if (indices.size() == 1) {
                result.add(-1);
            }
            else {
                int currentIndex = binarySearch(indices, 0, indices.size() - 1, query);
                if (currentIndex == indices.size() - 1) {
                    int next = numsLength - indices.get(currentIndex) + indices.get(0);
                    int previous = indices.get(currentIndex) - indices.get(currentIndex - 1);
                    result.add(Math.min(next, previous));
                }
                else if (currentIndex == 0) {
                    int next = indices.get(currentIndex + 1) - indices.get(currentIndex);
                    int previous = numsLength - indices.get(indices.size() - 1) + indices.get(currentIndex);
                    result.add(Math.min(next, previous));
                }
                else {
                    int previous = indices.get(currentIndex) - indices.get(currentIndex - 1);
                    int next = indices.get(currentIndex + 1) - indices.get(currentIndex);
                    result.add(Math.min(next, previous));
                }
            }
        }
        return result;
    }

    private int binarySearch(List<Integer> indices, int low, int high, int key) {
        while (low <= high) {
            int middle = low + (high - low) / 2;
            if (indices.get(middle) == key) {
                return middle;
            }
            if (indices.get(middle) > key) {
                high = middle - 1;
            }
            else {
                low = middle + 1;
            }
        }
        return -1;
    }
}