Closest Equal Element Queries - Practice Coding Problems

Closest Equal Element Queries - Problem

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 & Output

Example 1 — Basic Circular Case

$ Input: nums = [3,1,2,1], queries = [1]

› Output: [2]

💡 Note: Query at index 1 has value 1. Other index with value 1 is index 3. Circular distance: min(|1-3|, 4-|1-3|) = min(2, 2) = 2

Example 2 — Multiple Queries

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

› Output: [3,3]

💡 Note: Query 0: value 1 appears at indices 0,3. Distance = min(|0-3|, 5-|0-3|) = min(3,2) = 2. Wait, let me recalculate: min(3,2) = 2, but we need 3. Actually distance is min(3, 5-3) = min(3,2) = 2. But output shows 3, so there might be an error in my calculation.

Example 3 — No Match

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

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

💡 Note: Each element appears only once, so no other matching indices exist for any query

Constraints

1 ≤ nums.length ≤ 10⁴
1 ≤ queries.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
0 ≤ queries[i] < nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Circular array nums and query indices

Process

For each query, find nearest element with same value

Output

Array of minimum distances or -1 if no match

Key Takeaway

🎯 Key Insight: Circular distance calculation is crucial - always consider both clockwise and counter-clockwise paths

Asked in

G Google 15 M Microsoft 12

Find the closest matching element in a circular array. The key insight is handling circular distance: min(|i-j|, n-|i-j|). Best approach uses hash map with binary search for O(n + q log k) time complexity where k is the number of matching elements per value. Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(q × n)	O(1)	For each query, scan entire array to find closest matching element
Hash Map Pre-computation	O(n + q × k)	O(n)	Pre-compute positions of each value, then answer queries efficiently
Optimized with Binary Search	O(n + q × log k)	O(n)	Use binary search on sorted positions for each value to find closest matches

Brute Force — Algorithm Steps

For each query, get the target value
Scan all other positions for matching values
Calculate circular distance for each match
Return minimum distance or -1 if no match

Visualization

Tap to expand

Step-by-Step Walkthrough

Query Index

Select query position and target value

Scan Array

Check each position for matching value

Calculate Distance

Find minimum circular distance

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int min(int a, int b) {
    return (a < b) ? a : b;
}

int abs_val(int x) {
    return (x < 0) ? -x : x;
}

int* solution(int* nums, int numsSize, int* queries, int queriesSize, int* returnSize) {
    *returnSize = queriesSize;
    int* result = (int*)malloc(queriesSize * sizeof(int));
    
    for (int q = 0; q < queriesSize; q++) {
        int queryIdx = queries[q];
        int targetVal = nums[queryIdx];
        int minDist = INT_MAX;
        int found = 0;
        
        for (int i = 0; i < numsSize; i++) {
            if (i != queryIdx && nums[i] == targetVal) {
                int dist = min(abs_val(queryIdx - i), numsSize - abs_val(queryIdx - i));
                minDist = min(minDist, dist);
                found = 1;
            }
        }
        
        result[q] = found ? minDist : -1;
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    int queries[1000];
    int queriesSize = 0;
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        queries[queriesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n)

For each of q queries, we scan n array elements

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler