LeetCode 3488 - Closest Equal Element Queries

The problem asks us to process a series of queries on a circular array nums. Each query specifies an index, and for that index, we need to find the minimum circular distance to any other index with the same value.

leetcodemediumarrayhash-tablebinary-search

LeetCode Problem 3488

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search

Solution

Problem Understanding

The problem asks us to process a series of queries on a circular array nums. Each query specifies an index, and for that index, we need to find the minimum circular distance to any other index with the same value. The circular distance means that after the last element, the array wraps back to the first element. If no other index contains the same value, the result is -1.

The input consists of nums, an array of integers, and queries, an array of indices into nums. The output is an array answer where answer[i] is the minimum distance for query i.

The constraints are notable: nums can have up to 10^5 elements, and each number in nums can be as large as 10^6. This indicates that a naive solution iterating through the array for each query (O(n * q)) will likely be too slow. We need a more efficient approach, ideally using a preprocessed structure like a hash table for fast lookups.

Important edge cases include: all unique elements, queries pointing to the first or last index, and multiple occurrences of a value spread across the array in a circular manner.

Approaches

The brute-force approach would iterate over all indices of nums for each query and compute the circular distance to every other index containing the same value. This works correctly but requires O(n * q) time, which is too slow when both n and q are large.

The optimal approach leverages hash maps and binary search. We first map each value in nums to a sorted list of all indices where it occurs. Then, for a query, we find the closest index to the queried position using binary search in that list. Since the array is circular, we consider distances both forward and backward by also virtually adding the length of the array to the indices to handle wrap-around cases. This reduces the complexity to O(n + q * log k) where k is the number of occurrences of a value.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * q) O(1) Iterates all other indices for each query
Optimal O(n + q * log k) O(n) Uses hash map of value -> sorted index list and binary search

Algorithm Walkthrough

  1. Initialize a hash map value_indices to store each value in nums as a key and a sorted list of its indices as the value. Iterate over nums once to populate this map.
  2. For each query qi in queries, retrieve the value v = nums[qi]. If v occurs only once, set the answer to -1.
  3. If there are multiple indices for v, perform a binary search in the sorted list of indices to find the nearest index before or after qi.
  4. Compute the circular distance between qi and candidate indices. Since the array is circular, the distance is min(abs(a - b), n - abs(a - b)).
  5. Store the minimum distance in the result array.
  6. Return the result array after processing all queries.

Why it works: The hash map ensures constant-time access to the relevant indices, while the sorted list and binary search provide an efficient way to find the closest index. Considering the circular distance formula guarantees that wrap-around distances are accounted for.

Python Solution

from typing import List
import bisect

class Solution:
    def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        value_indices = {}
        
        for i, num in enumerate(nums):
            if num not in value_indices:
                value_indices[num] = []
            value_indices[num].append(i)
        
        answer = []
        for qi in queries:
            v = nums[qi]
            indices = value_indices[v]
            if len(indices) == 1:
                answer.append(-1)
                continue
            
            # Binary search for closest index
            pos = bisect.bisect_left(indices, qi)
            # Circular distance candidates
            prev_idx = indices[pos - 1] if pos > 0 else indices[-1]
            next_idx = indices[pos] if pos < len(indices) else indices[0]
            
            dist_prev = min(abs(qi - prev_idx), n - abs(qi - prev_idx))
            dist_next = min(abs(qi - next_idx), n - abs(qi - next_idx))
            
            answer.append(min(dist_prev, dist_next))
        
        return answer

Explanation: The Python solution builds a mapping from values to all indices in nums. For each query, we check the list of indices. If the list has only one element, we return -1. Otherwise, we find the nearest index using bisect, compute circular distances, and choose the smaller one. This approach efficiently handles the circular nature of the array.

Go Solution

package main

import (
	"sort"
)

func solveQueries(nums []int, queries []int) []int {
	n := len(nums)
	valueIndices := make(map[int][]int)
	for i, num := range nums {
		valueIndices[num] = append(valueIndices[num], i)
	}

	answer := make([]int, len(queries))
	for i, qi := range queries {
		v := nums[qi]
		indices := valueIndices[v]
		if len(indices) == 1 {
			answer[i] = -1
			continue
		}
		pos := sort.Search(len(indices), func(j int) bool { return indices[j] >= qi })
		
		prevIdx := indices[(pos-1+len(indices))%len(indices)]
		nextIdx := indices[pos%len(indices)]
		
		distPrev := min(abs(qi-prevIdx), n-abs(qi-prevIdx))
		distNext := min(abs(qi-nextIdx), n-abs(qi-nextIdx))
		answer[i] = min(distPrev, distNext)
	}
	return answer
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

Explanation: The Go solution mirrors the Python approach. We use map[int][]int to store indices and sort.Search for binary search. Circular indices are handled using modulo arithmetic. abs and min helpers simplify distance calculations.

Worked Examples

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

Query Value Indices Closest Index Distance Answer
0 1 [0,2,4] 2 2 2
3 4 [3] - - -1
5 3 [1,5] 1 3 3

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

All values are unique, so the answer is [-1,-1,-1,-1].

Complexity Analysis

Measure Complexity Explanation
Time O(n + q * log k) n for building the map, q queries, each with log k binary search
Space O(n) Storing indices of all elements in a hash map

The time complexity is efficient for large n and q. Space is linear in the array size, which is acceptable under constraints.

Test Cases

# Provided examples
assert Solution().solveQueries([1,3,1,4,1,3,2], [0,3,5]) == [2,-1,3]  # multiple occurrences and circular distance
assert Solution().solveQueries([1,2,3,4], [0,1,2,3]) == [-1,-1,-1,-1]  # all unique

# Edge cases
assert Solution().solveQueries([1,1], [0,1]) == [1,1]  # smallest array with duplicates
assert Solution().solveQueries([2,2,2,2], [0,1,2,3]) == [1,1,1,1]  # all identical
assert Solution().solveQueries([1,2,3,1,2,3], [0,3,2,5]) == [3,3,3,3]  # multiple wrap-around distances
Test Why
[1,3,1,4,1,3,2], [0,3,5] Normal case with duplicates and circular distances
[1,2,3,4], [0,1,2,3] Unique elements return -1
[1,1], [0,1] Smallest array with duplicates to test minimal input
[2,2,2,2], [0,1,2,3] All identical, check consistent circular distance
[1,2,3,1,2,3], [0,3,2,5] Wrap-around distances for multiple occurrences

Edge Cases

One edge case is when `