LeetCode 3488 – Closest Equal Element Queries
Closest Equal Element Queries
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.
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.Input: nums = [1, 3, 1, 4, 1, 3, 2] · queries = [0, 3, 5]
Expected Output: [2, −1, 3]
Clockwise to index 2: 0 → 1 → 2 = 2 steps. Counter-clockwise to index 4: 0 → 6 → 5 → 4 = 3 steps. Min = 2.
Value 4 appears exactly once in the entire array. No other index shares this value anywhere — circular search finds nothing.
Match at index 1. Clockwise: 5 → 6 → 0 → 1 = 3 steps. Counter-clockwise: 5 → 4 → 3 → 2 → 1 = 4 steps. Min = 3.
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.
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.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).
int n = nums.length; int m = n * 2; int[] d = new int[m]; Arrays.fill(d, m); // ∞ sentinel
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.
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); }
d[5] = 4 for query index 5 (value 3) — but this is the linear distance, not the shorter circular one yet.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.
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); }
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.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.
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;
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; } }
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.1. Brute Force
O(n × q) time · O(1) spaceFor each query, iterate through every other index, compute circular distance, track minimum.
- Simplest to write and understand
- No extra data structures needed
- O(n×q) — TLEs on large inputs
- Redundant work repeated per query
2. Precompute + Binary Search
O((n + q) log n) time · O(n) spaceGroup 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.
- Handles many queries efficiently
- Good when duplicates are sparse
- Binary search overhead per query
- Fiddly wrap-around edge cases
3. Double Array + Two Hash-Map Sweeps
O(n + q) time · O(n) spaceDoubles the array to flatten circular logic, then runs two linear sweeps to precompute min distance for every position. Answers each query in O(1).
- Fully linear — optimal
- Clean two-pass pattern
- All edge cases handled elegantly
- Uses 2× memory for doubled array
- "Why double?" step needs explanation
4. Multi-Source BFS on Circular Graph
O(n + q) time · O(n) spaceModel the circular array as a graph. Run BFS from all positions sharing the same value simultaneously, spreading minimum distances outward.
- Generalizes to 2D / graph variants
- Intuitive if graph-thinking is natural
- Queue overhead makes it slower in practice
- Overkill for this 1D problem