By Expert Funda Thursday, April 16, 2026

#3488 Medium Array Hash Map Two Pass Circular Array

Closest Equal Element Queries

O(n + q) optimal Java · Hash Map · Double Array Circular Distance Trick
📋
Problem Statement

You are given a circular array nums and an array of queries, where each query is an index into nums.

For each queries[i], find the minimum circular distance to any other index j where nums[j] == nums[queries[i]]. If no such index exists, return -1.

🔵
Circular distance between indices i and j in an array of length n is min(|i − j|, n − |i − j|). You can go clockwise or counter-clockwise — whichever is shorter.
circDist(i, j) = min( |i − j| , n − |i − j| )
💡
Think of the array as a clock face. From 3 to 11 you can go 8 steps one way or 4 steps the other — you always take the shorter route.
🔍
Example Breakdown

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

Expected Output: [2, −1, 3]

1
0
3
1
1
2
4
3
1
4
3
5
2
6
Queried index Matching value
Query 0 index = 0  |  value = 1
1
0
3
1
1
2
4
3
1
4
3
5
2
6

Clockwise to index 2: 0 → 1 → 2 = 2 steps. Counter-clockwise to index 4: 0 → 6 → 5 → 4 = 3 steps. Min = 2.

answer = 2
Query 1 index = 3  |  value = 4
1
0
3
1
1
2
4
3
1
4
3
5
2
6

Value 4 appears exactly once in the entire array. No other index shares this value anywhere — circular search finds nothing.

answer = −1
Query 2 index = 5  |  value = 3
1
0
3
1
1
2
4
3
1
4
3
5
2
6

Match at index 1. Clockwise: 5 → 6 → 0 → 1 = 3 steps. Counter-clockwise: 5 → 4 → 3 → 2 → 1 = 4 steps. Min = 3.

answer = 3
Traversed path
💡
Intuition Behind the Solution

For any index i, the nearest equal element is either somewhere to its left or somewhere to its right in the circular order. If we precompute both directions for every position upfront, answering queries becomes an O(1) lookup.

🔑
Key insight — Double the array: Instead of writing special circular-wrap logic, extend nums to length 2n by appending a copy. Any circular neighbor of index i in the original ring appears within distance n in this doubled array. Wrap-around is now just a straight path in the second copy.
nums = [1, 3, 1, 4, 1, 3, 2] → doubled to length 14
index
0
1
2
3
4
5
6
7
8
9
10
11
12
13
nums[i%n]
1
3
1
4
1
3
2
1
3
1
4
1
3
2
← → Left pass
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
→ ← Right pass
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
✓
Original copy Mirror copy n=7 boundary
🧭
Step-by-Step Algorithm
Left-to-right pass on doubled array — click NEXT to step through
Ready — press Next to begin the left pass
1

Double the array, init distance array

Create a virtual doubled array of length m = 2n using nums[i % n]. Initialize d[m] filled with m (acts as ∞, since no real distance can reach it).

Java
int n = nums.length;
int m = n * 2;
int[] d = new int[m];
Arrays.fill(d, m); // ∞ sentinel
2

Left-to-right pass

Scan i = 0 → m−1. A hash map left tracks the last index where each value was seen. Whenever we encounter a repeated value, we record d[i] = min(d[i], i − left.get(val)), then update the map.

Java
Map<Integer, Integer> left = new HashMap<>();
for (int i = 0; i < m; i++) {
    int val = nums[i % n];
    if (left.containsKey(val))
        d[i] = Math.min(d[i], i - left.get(val));
    left.put(val, i);
}
→
This sweep finds the nearest equal element looking left (or wrap-around via the second copy). After this pass, d[5] = 4 for query index 5 (value 3) — but this is the linear distance, not the shorter circular one yet.
3

Right-to-left pass

Scan i = m−1 → 0 with another map right. Same logic in reverse — this finds the nearest equal element looking right, capturing the shorter counter-clockwise path.

Java
Map<Integer, Integer> right = new HashMap<>();
for (int i = m - 1; i >= 0; i--) {
    int val = nums[i % n];
    if (right.containsKey(val))
        d[i] = Math.min(d[i], right.get(val) - i);
    right.put(val, i);
}
←
After this pass, d[5] is updated from 4 to 3. At index 5, value 3 appears next at index 8 (the mirror). Distance = 8 − 5 = 3. This is the circular path 5 → 6 → 0 → 1.
4

Answer each query

For query index q, combine both halves: min(d[q], d[q + n]). If the result ≥ n, the value appears only once → return −1.

Java
int[] ans = new int[queries.length];
for (int k = 0; k < queries.length; k++) {
    int q = queries[k];
    int best = Math.min(d[q], d[q + n]);
    ans[k] = (best >= n) ? -1 : best;
}
return ans;
☕
Complete Java Solution
Java 
import java.util.*;

class Solution {
    public int[] solveQueries(int[] nums, int[] queries) {
        int n = nums.length;
        int m = n * 2;            // doubled array length

        int[] d = new int[m];
        Arrays.fill(d, m);        // init all distances to ∞ (= m)

        // ── Pass 1: left → right ─────────────────────────────
        Map<Integer, Integer> left = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int val = nums[i % n];          // circular access via modulo
            if (left.containsKey(val)) {
                d[i] = Math.min(d[i], i - left.get(val));
            }
            left.put(val, i);               // update last seen position
        }

        // ── Pass 2: right → left ─────────────────────────────
        Map<Integer, Integer> right = new HashMap<>();
        for (int i = m - 1; i >= 0; i--) {
            int val = nums[i % n];
            if (right.containsKey(val)) {
                d[i] = Math.min(d[i], right.get(val) - i);
            }
            right.put(val, i);
        }

        // ── Answer queries ────────────────────────────────────
        int[] ans = new int[queries.length];
        for (int k = 0; k < queries.length; k++) {
            int q = queries[k];
            // combine both halves; if still ≥ n → value is unique → -1
            int best = Math.min(d[q], d[q + n]);
            ans[k] = (best >= n) ? -1 : best;
        }
        return ans;
    }
}
O(n + q)
Time
O(n)
Space
2 passes
Sweeps
⚠️
Why min(d[q], d[q+n])? The left pass updates d[i] when it finds a left-side match. d[q+n] catches any circular path that the right copy exposed. Taking the min of both gives you the true circular minimum.
⚖️
All Approaches — Pros & Cons

1. Brute Force

O(n × q) time · O(1) space

For each query, iterate through every other index, compute circular distance, track minimum.

Pros
  • Simplest to write and understand
  • No extra data structures needed
Cons
  • O(n×q) — TLEs on large inputs
  • Redundant work repeated per query

2. Precompute + Binary Search

O((n + q) log n) time · O(n) space

Group all indices by value into sorted lists. For each query, binary search the list to find the nearest neighbor, then check both sides plus wrap-around.

Pros
  • Handles many queries efficiently
  • Good when duplicates are sparse
Cons
  • Binary search overhead per query
  • Fiddly wrap-around edge cases

3. Double Array + Two Hash-Map Sweeps

O(n + q) time · O(n) space

Doubles the array to flatten circular logic, then runs two linear sweeps to precompute min distance for every position. Answers each query in O(1).

Pros
  • Fully linear — optimal
  • Clean two-pass pattern
  • All edge cases handled elegantly
Cons
  • Uses 2× memory for doubled array
  • "Why double?" step needs explanation

4. Multi-Source BFS on Circular Graph

O(n + q) time · O(n) space

Model the circular array as a graph. Run BFS from all positions sharing the same value simultaneously, spreading minimum distances outward.

Pros
  • Generalizes to 2D / graph variants
  • Intuitive if graph-thinking is natural
Cons
  • Queue overhead makes it slower in practice
  • Overkill for this 1D problem
Continue Reading →