Closest Equal Element Queries

Medium
1829.

Closest Equal Element Queries

Closest Equal Element Queries is a medium coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.

You are given a circular array nums (the element after the last one is the first one) and an array queries of indices into it.

For each query index i, find the minimum distance from i to any other index j with nums[j] == nums[i]. Distances are measured around the circle: between i and j it is min(|i - j|, n - |i - j|). If no other index holds the same value, the answer is -1.

Return the answers in the order of queries.

Example 1

Input
nums = [5,2,5,7,2,5], queries = [0,3,4]
Output
[1,-1,3]
Explanation
Index 0 reaches the `5` at index 5 by wrapping around (distance 1). `7` occurs once. The other `2` is 3 steps away either way.

Example 2

Input
nums = [1,2,3,4], queries = [0,1,2,3]
Output
[-1,-1,-1,-1]
Explanation
Every value is unique.

Example 3

Input
nums = [8,8], queries = [1]
Output
[1]

Constraints

  • 1 <= queries.length <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6
  • 0 <= queries[i] < nums.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} queries
 * @return {number[]}
 */
var solveQueries = function(nums, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Closest Equal Element Queries — Problem & Solution

Closest Equal Element Queries solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Closest Equal Element Queries is a medium coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Binary Search
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a circular array nums (the element after the last one is the first one) and an array queries of indices into it.

For each query index i, find the minimum distance from i to any other index j with nums[j] == nums[i]. Distances are measured around the circle: between i and j it is min(|i - j|, n - |i - j|). If no other index holds the same value, the answer is -1.

Return the answers in the order of queries.

Example 1

Input: nums = [5,2,5,7,2,5], queries = [0,3,4]
Output: [1,-1,3]
Explanation: Index 0 reaches the `5` at index 5 by wrapping around (distance 1). `7` occurs once. The other `2` is 3 steps away either way.

Example 2

Input: nums = [1,2,3,4], queries = [0,1,2,3]
Output: [-1,-1,-1,-1]
Explanation: Every value is unique.

Example 3

Input: nums = [8,8], queries = [1]
Output: [1]

Constraints

  • 1 <= queries.length <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6
  • 0 <= queries[i] < nums.length

Hints for Closest Equal Element Queries

  1. Hint 1

    Group the indices by value. Inside one group, which other index can be closest to a given index on the circle?

  2. Hint 2

    Sort each group's indices. The closest equal element is always one of the two neighbours in that sorted list — treating the list itself as circular, so the first and last indices are neighbours too.

  3. Hint 3

    Precompute the answer for every index once (-1 for groups of size 1), then answer each query by lookup.

How to solve Closest Equal Element Queries

On a circle, the nearest index holding the same value is the next or previous occurrence of that value going around. Listing each value's indices in increasing order makes those two occurrences neighbours in the list, with wrap-around.

Approach

  1. Collect, for each value, the list of indices where it occurs (in increasing order).
  2. For a list of size 1, its index answers -1.
  3. For a list idx of size m >= 2, each idx[t] answers the smaller circular distance to idx[t - 1] and idx[t + 1], indices taken modulo m.
  4. Return answer[queries[k]] for each query.

Why it works

Walking clockwise from i, the first equal value met is the next occurrence in sorted order (or the first one, after wrapping). Walking counter-clockwise it is the previous occurrence. The circular distance to any other occurrence is at least the walk to one of these two, because reaching it requires passing one of them first in the direction of the shorter arc.

Complexity

  • Time — O(n log n) with sorting, or O(n) with a hash map filled left to right
  • Space — O(n)

Pitfalls

  • Forgetting the wrap-around neighbour: the first and last occurrences can be adjacent across the end of the array.
  • The distance itself is also circular: take min(d, n - d).
  • Answering each query by scanning the array is O(n * q) — too slow at 10^5.

Reference solution

Python

from typing import List

def solveQueries(nums: List[int], queries: List[int]) -> List[int]:
    n = len(nums)
    groups = {}
    for i, v in enumerate(nums):
        groups.setdefault(v, []).append(i)
    best = [-1] * n
    for idx in groups.values():
        m = len(idx)
        if m < 2:
            continue
        for t in range(m):
            i = idx[t]
            for j in (idx[t - 1], idx[(t + 1) % m]):
                d = abs(i - j)
                d = min(d, n - d)
                if best[i] < 0 or d < best[i]:
                    best[i] = d
    return [best[q] for q in queries]

Java

public static int[] solveQueries(int[] nums, int[] queries) {
    int n = nums.length;
    Map<Integer, List<Integer>> groups = new HashMap<>();
    for (int i = 0; i < n; i++) groups.computeIfAbsent(nums[i], x -> new ArrayList<>()).add(i);
    int[] best = new int[n];
    Arrays.fill(best, -1);
    for (List<Integer> idx : groups.values()) {
        int m = idx.size();
        if (m < 2) continue;
        for (int t = 0; t < m; t++) {
            int a = idx.get(t);
            int[] nb = { idx.get((t - 1 + m) % m), idx.get((t + 1) % m) };
            for (int j : nb) {
                int d = Math.abs(a - j);
                d = Math.min(d, n - d);
                if (best[a] < 0 || d < best[a]) best[a] = d;
            }
        }
    }
    int[] out = new int[queries.length];
    for (int q = 0; q < queries.length; q++) out[q] = best[queries[q]];
    return out;
}

C++

vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
    int n = nums.size();
    unordered_map<int, vector<int>> groups;
    for (int i = 0; i < n; i++) groups[nums[i]].push_back(i);
    vector<int> best(n, -1);
    for (auto& kv : groups) {
        vector<int>& idx = kv.second;
        int m = idx.size();
        if (m < 2) continue;
        for (int t = 0; t < m; t++) {
            int a = idx[t];
            int nb[2] = { idx[(t - 1 + m) % m], idx[(t + 1) % m] };
            for (int j : nb) {
                int d = abs(a - j);
                d = min(d, n - d);
                if (best[a] < 0 || d < best[a]) best[a] = d;
            }
        }
    }
    vector<int> out;
    for (int q : queries) out.push_back(best[q]);
    return out;
}

JavaScript

var solveQueries = function(nums, queries) {
    var n = nums.length;
    var groups = new Map();
    for (var i = 0; i < n; i++) {
        var g = groups.get(nums[i]);
        if (!g) { g = []; groups.set(nums[i], g); }
        g.push(i);
    }
    var best = new Array(n).fill(-1);
    groups.forEach(function(idx) {
        var m = idx.length;
        if (m < 2) return;
        for (var t = 0; t < m; t++) {
            var a = idx[t];
            var nb = [idx[(t - 1 + m) % m], idx[(t + 1) % m]];
            for (var k = 0; k < 2; k++) {
                var d = Math.abs(a - nb[k]);
                d = Math.min(d, n - d);
                if (best[a] < 0 || d < best[a]) best[a] = d;
            }
        }
    });
    var out = [];
    for (var q = 0; q < queries.length; q++) out.push(best[queries[q]]);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets