Closest Equal Element Queries
MedPrompt
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 indexjin the circular array, wherenums[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.
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] = 0isnums[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] = 3isnums[3] = 4. No other index contains 4, so the result is -1. - Query 2: The element at
queries[2] = 5isnums[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 <= 1051 <= nums[i] <= 1060 <= queries[i] < nums.length
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. For each query, it iterates through the entire nums array to find all other elements equal to the one at the queried index. It calculates the circular distance to each of these matching elements and keeps track of the minimum distance found.
Algorithm
- Initialize an
answerarray of the same size asqueries. - Let
nbe the length ofnums. - For each
ifrom0toqueries.length - 1:- Let
queryIndex = queries[i]. - Let
targetVal = nums[queryIndex]. - Initialize
minDist = Integer.MAX_VALUE. - For each
jfrom0ton - 1:- If
j == queryIndex, continue. - If
nums[j] == targetVal:dist = Math.abs(queryIndex - j).circularDist = Math.min(dist, n - dist).minDist = Math.min(minDist, circularDist).
- If
- Set
answer[i]tominDistif it was updated, otherwise set it to-1.
- Let
- Return
answer.
Walkthrough
The algorithm processes one query at a time. For a given queryIndex, it first identifies the target value val = nums[queryIndex]. It then loops through every other index j in the nums array. If nums[j] is equal to val, it calculates the distance between queryIndex and j. Since the array is circular, the distance between two indices i and j in an array of length n is min(|i - j|, n - |i - j|). A variable minDist is maintained to store the minimum distance found so far for the current query. It's initialized to a very large value. After checking all indices, if minDist remains at its initial large value, it means no other equal element was found, and the result is -1. Otherwise, the result is minDist. This process is repeated for all queries.
class Solution { public int[] closestEqualElements(int[] nums, int[] queries) { int n = nums.length; int q = queries.length; int[] answer = new int[q]; for (int i = 0; i < q; i++) { int queryIndex = queries[i]; int targetVal = nums[queryIndex]; int minDistance = Integer.MAX_VALUE; for (int j = 0; j < n; j++) { if (j == queryIndex) { continue; } if (nums[j] == targetVal) { int dist = Math.abs(queryIndex - j); int circularDist = Math.min(dist, n - dist); minDistance = Math.min(minDistance, circularDist); } } if (minDistance == Integer.MAX_VALUE) { answer[i] = -1; } else { answer[i] = minDistance; } } return answer; }}Complexity
Time
O(Q * N), where `Q` is the number of queries and `N` is the length of `nums`. For each of the `Q` queries, we perform a linear scan of the `N` elements.
Space
O(Q) for the answer array. If we exclude the output array, the space complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Requires minimal extra space.
Cons
Very inefficient due to nested loops.
Will result in a 'Time Limit Exceeded' error for large inputs as per the problem constraints.
This approach improves upon the brute-force method by avoiding the repeated scanning of the nums array. It first preprocesses the nums array to store the indices of each unique value in a hash map. The lists of indices are inherently sorted. For each query, it uses binary search on the corresponding list of indices to efficiently find the nearest neighbors.
Algorithm
- Create a
Map<Integer, List<Integer>> valToIndices. - Iterate
ifrom0tonums.length - 1and populate the map:valToIndices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i). - Initialize an
answerarray. - For each
queryIndexinqueries:- Get
val = nums[queryIndex]andindices = valToIndices.get(val). - If
indices.size() <= 1, the answer is -1. - Otherwise, find the position of
queryIndexinindicesusing binary search, let it belistIdx. - Get the predecessor index in
nums:prevNumIndex = indices.get((listIdx - 1 + indices.size()) % indices.size()). - Get the successor index in
nums:nextNumIndex = indices.get((listIdx + 1) % indices.size()). - Calculate left distance:
distLeft = (queryIndex - prevNumIndex + n) % n. - Calculate right distance:
distRight = (nextNumIndex - queryIndex + n) % n. - The answer is
Math.min(distLeft, distRight).
- Get
- Return
answer.
Walkthrough
Preprocessing:
- Create a hash map,
valToIndices, where keys are the integer values fromnumsand values are lists of indices where those values appear. - Iterate through
nums. For each elementnums[i], add the indexito the list associated withnums[i]in the map. Since we iterate fromi=0ton-1, the lists of indices will be sorted.
Query Processing:
- For each
queryIndexinqueries, get the valueval = nums[queryIndex]. - Retrieve the list of indices,
indicesList, forvalfrom the hash map. - If
indicesListcontains one or zero elements, no other equal element exists, so the answer is -1. - Otherwise, the closest indices to
queryIndexmust be its immediate predecessor and successor in the sortedindicesList. The circular nature of the array means the predecessor of the first element is the last, and the successor of the last is the first. - Use binary search (
Collections.binarySearch) to find the position ofqueryIndexwithinindicesList. Let this position belistIdx. - Identify the predecessor index in
nums(prevNumIndex) and the successor index (nextNumIndex) usinglistIdxand handling wrap-around. - The distance to the left neighbor is
(queryIndex - prevNumIndex + n) % n. - The distance to the right neighbor is
(nextNumIndex - queryIndex + n) % n. - The minimum of these two distances is the answer for the query.
import java.util.*; class Solution { public int[] closestEqualElements(int[] nums, int[] queries) { int n = nums.length; int q = queries.length; Map<Integer, List<Integer>> valToIndices = new HashMap<>(); for (int i = 0; i < n; i++) { valToIndices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i); } int[] answer = new int[q]; for (int i = 0; i < q; i++) { int queryIndex = queries[i]; int val = nums[queryIndex]; List<Integer> indices = valToIndices.get(val); if (indices.size() <= 1) { answer[i] = -1; continue; } int listIdx = Collections.binarySearch(indices, queryIndex); int listSize = indices.size(); int prevNumIndex = indices.get((listIdx - 1 + listSize) % listSize); int nextNumIndex = indices.get((listIdx + 1) % listSize); int distLeft = (queryIndex - prevNumIndex + n) % n; int distRight = (nextNumIndex - queryIndex + n) % n; answer[i] = Math.min(distLeft, distRight); } return answer; }}Complexity
Time
O(N + Q * log N). `O(N)` for preprocessing the `nums` array into the hash map. For each of the `Q` queries, we perform a binary search on a list of indices, which takes `O(log k)` time, where `k` is the number of occurrences of the value. In the worst case, `k` can be up to `N`.
Space
O(N) to store the hash map. In the worst case, every element is distinct, and the map stores `N` keys, each with a list of one index.
Trade-offs
Pros
Significantly faster than the brute-force approach.
Efficient enough to pass the given constraints.
Cons
Requires extra space for the hash map.
This is the most optimal approach. Instead of calculating the answer for each query as it comes, we can pre-calculate the answer for every possible index in the nums array. This way, answering the queries becomes a simple lookup in the pre-calculated results array.
Algorithm
- Create a
Map<Integer, List<Integer>> valToIndicesand populate it by iterating throughnums. - Initialize an
allAnswersarray of sizenwith-1. - Let
n = nums.length. - For each
List<Integer> indicesinvalToIndices.values():- If
indices.size() <= 1, continue. - Let
listSize = indices.size(). - For
jfrom0tolistSize - 1:currentIndex = indices.get(j).prevIndex = indices.get((j - 1 + listSize) % listSize).nextIndex = indices.get((j + 1) % listSize).distLeft = (currentIndex - prevIndex + n) % n.distRight = (nextIndex - currentIndex + n) % n.allAnswers[currentIndex] = Math.min(distLeft, distRight).
- If
- Create a
resultarray of sizequeries.length. - For
ifrom0toqueries.length - 1:result[i] = allAnswers[queries[i]].
- Return
result.
Walkthrough
The core idea is to compute the closest distance for every index i from 0 to n-1 and store it in an allAnswers array.
Preprocessing:
- First, just like the previous approach, we create a hash map
valToIndicesto group indices by their values. This takesO(N)time.
Answer Calculation:
- Initialize an
allAnswersarray of sizenwith a default value of -1. - Iterate through each list of indices in the
valToIndicesmap. - For each
indicesListthat has more than one element:- Iterate through the
indicesList. For eachcurrentIndexat positionjin the list: - Find its predecessor
prevIndexand successornextIndexin the list, handling wrap-around for the first and last elements. - The predecessor is at
indicesList.get((j - 1 + size) % size). - The successor is at
indicesList.get((j + 1) % size). - Calculate the distance to the left neighbor:
distLeft = (currentIndex - prevIndex + n) % n. - Calculate the distance to the right neighbor:
distRight = (nextIndex - currentIndex + n) % n. - The minimum distance for
currentIndexismin(distLeft, distRight). Store this value inallAnswers[currentIndex].
- Iterate through the
Query Resolution:
- After the
allAnswersarray is fully computed, iterate through thequeriesarray. - For each
queryIndex, the result is simplyallAnswers[queryIndex].
import java.util.*; class Solution { public int[] closestEqualElements(int[] nums, int[] queries) { int n = nums.length; Map<Integer, List<Integer>> valToIndices = new HashMap<>(); for (int i = 0; i < n; i++) { valToIndices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i); } int[] allAnswers = new int[n]; Arrays.fill(allAnswers, -1); for (List<Integer> indices : valToIndices.values()) { int listSize = indices.size(); if (listSize <= 1) { continue; } for (int i = 0; i < listSize; i++) { int currentIndex = indices.get(i); int prevIndex = indices.get((i - 1 + listSize) % listSize); int nextIndex = indices.get((i + 1) % listSize); int distLeft = (currentIndex - prevIndex + n) % n; int distRight = (nextIndex - currentIndex + n) % n; allAnswers[currentIndex] = Math.min(distLeft, distRight); } } int q = queries.length; int[] result = new int[q]; for (int i = 0; i < q; i++) { result[i] = allAnswers[queries[i]]; } return result; }}Complexity
Time
O(N + Q). `O(N)` to build the map. `O(N)` to iterate through all the indices in the map's values to compute `allAnswers` (since the total number of indices is `N`). `O(Q)` to build the final result from `allAnswers`.
Space
O(N + Q). `O(N)` for the hash map, `O(N)` for the `allAnswers` array, and `O(Q)` for the result array. If we exclude the output array, it's `O(N)`.
Trade-offs
Pros
Most efficient time complexity, as it's linear with respect to the input sizes.
Queries are answered in O(1) time after pre-computation.
Cons
Uses more space than the binary search approach due to the
allAnswersarray.
Solutions
Solution
class Solution {public List<Integer> solveQueries(int[] nums, int[] queries) { int n = nums.length; int m = n * 2; int[] d = new int[m]; Arrays.fill(d, m); Map<Integer, Integer> left = new HashMap<>(); for (int i = 0; i < m; i++) { int x = nums[i % n]; if (left.containsKey(x)) { d[i] = Math.min(d[i], i - left.get(x)); } left.put(x, i); } Map<Integer, Integer> right = new HashMap<>(); for (int i = m - 1; i >= 0; i--) { int x = nums[i % n]; if (right.containsKey(x)) { d[i] = Math.min(d[i], right.get(x) - i); } right.put(x, i); } for (int i = 0; i < n; i++) { d[i] = Math.min(d[i], d[i + n]); } List<Integer> ans = new ArrayList<>(); for (int query : queries) { ans.add(d[query] >= n ? -1 : d[query]); } return ans; }}class Solution {public: vector<int> solveQueries(vector<int> &nums, vector<int> &queries) { int n = nums.size(); int m = n * 2; vector<int> d(m, m); unordered_map<int, int> left; for (int i = 0; i < m; i++) { int x = nums[i % n]; if (left.count(x)) { d[i] = min(d[i], i - left[x]); } left[x] = i; } unordered_map<int, int> right; for (int i = m - 1; i >= 0; i--) { int x = nums[i % n]; if (right.count(x)) { d[i] = min(d[i], right[x] - i); } right[x] = i; } for (int i = 0; i < n; i++) { d[i] = min(d[i], d[i + n]); } vector<int> ans; for (int query : queries) { ans.push_back(d[query] >= n ? -1 : d[query]); } return ans; }};class Solution: def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]: n = len(nums) m = n << 1 d = [m] * m left = {} for i in range(m): x = nums[i % n] if x in left: d[i] = min(d[i], i - left[x]) left[x] = i right = {} for i in range(m - 1, - 1, - 1): x = nums[i % n] if x in right: d[i] = min(d[i], right[x] - i) right[x] = i for i in range(n): d[i] = min(d[i], d[i + n]) return [- 1 if d[i] >= n else d[i] for i in queries]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.