Closest Equal Element Queries

Medium

Asked by:

3 views

Topics:

Arrays

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.

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] = 0 is nums[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] = 3 is nums[3] = 4. No other index contains 4, so the result is -1.
Query 2: The element at queries[2] = 5 is nums[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 <= 10⁵
1 <= nums[i] <= 10⁶
0 <= queries[i] < nums.length

Try coding it in LeetCode

Closest Equal Element Queries

Medium

Asked by:

3 views

Topics:

Arrays

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.

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] = 0 is nums[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] = 3 is nums[3] = 4. No other index contains 4, so the result is -1.
Query 2: The element at queries[2] = 5 is nums[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 <= 10⁵
1 <= nums[i] <= 10⁶
0 <= queries[i] < nums.length

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `nums` and `queries` arrays? What is the range of values within the `nums` array?
Could the `left` and `right` indices in a query be out of bounds for the `nums` array? If so, how should I handle those cases?
If there are multiple elements within the range [left, right] that have the same value as `nums[left]`, should I return the index of the *first* one encountered moving from `left + 1` to `right`, or is there another tie-breaker?
Is `left` always guaranteed to be less than or equal to `right` in each query?
What should I return if `left` equals `right` and `nums[left]` does not exist at another index within the range?

Brute Force Solution

Approach

The brute force approach to answering these questions is very direct. For each question, we simply search through the entire list of numbers. We'll find the two numbers closest to the question's position that match the question's value.

Here's how the algorithm would work step-by-step:

For each question you're asked, first grab the question's value and the question's position.
Start searching from the very beginning of the list of numbers.
Check each number in the list one by one to see if it matches the question's value.
If it matches, calculate how far away it is from the question's position.
Do the same going backwards from the end of the list of numbers toward the question's position.
Keep track of the closest number before the question's position and the closest number after the question's position that match.
Once you've looked at all the numbers, return the closest distances you found before and after.

Code Implementation

def closest_equal_element_queries_brute_force(elements, queries):
    results = []
    for query in queries:
        query_index = query[0]
        closest_index = -1
        min_distance = float('inf')

        # Iterate through all elements to find the closest equal element
        for element_index in range(len(elements)):

            # Check if the element's value matches the query value
            if elements[element_index] == elements[query_index]:

                distance = abs(element_index - query_index)
                #Find the element with minimal distance
                if distance < min_distance:
                    min_distance = distance
                    closest_index = element_index
        results.append(closest_index)
    return results

Big(O) Analysis

Time Complexity

O(n*q) – For each of the q queries, we iterate through the entire input array of n elements. Inside each query's iteration, we perform constant time operations to compare values and calculate distances. Therefore, the time complexity for a single query is O(n). Since we have to process q queries, the overall time complexity is O(n*q).

Space Complexity

O(1) – The provided brute force approach only utilizes a few constant space variables. Specifically, it stores the question's value, question's position, the closest distance before, and the closest distance after. Regardless of the input array's size (N), the algorithm only requires this fixed amount of extra space for storing these constant number of variables, making the space complexity O(1).

Optimal Solution

Approach

The key is to precompute and store the positions of each number in the original list. Then, for each query, we can quickly find the closest occurrences of the target number without iterating through the entire list repeatedly.

Here's how the algorithm would work step-by-step:

First, organize the original list by making a note of where each number appears. For example, if the list is [1, 2, 1, 3, 1], you'd note that '1' appears in positions 1, 3, and 5.
When you get a question asking for the closest occurrence of a number near a specific position, look up the list of positions for that number.
From the list of positions, find the position that's closest to the position specified in the question. This is faster than checking the entire list every time.
If there is no match, simply return an indicator that there is no value found

Code Implementation

def closest_equal_element_queries(numbers, queries):
    last_occurrence = {}
    result = []

    for index, number in enumerate(numbers):
        last_occurrence[number] = index

    for query_index, query_range in enumerate(queries):
        left_boundary, target_index = query_range
        minimum_distance = float('inf')
        found = False

        # Iterate through each unique number to find the closest
        for number, last_index in last_occurrence.items():

            # Check if the last seen index falls within the range
            if left_boundary <= last_index <= target_index:
                distance = abs(last_index - target_index)

                # Update the minimum distance if a closer element is found
                if distance < minimum_distance:
                    minimum_distance = distance
                    found = True

        # If no element found in range set -1, else shortest distance
        if not found:
            result.append(-1)
        else:
            result.append(minimum_distance)

    return result

Big(O) Analysis

Time Complexity

O(m log k) – The preprocessing step to store the positions of each number iterates through the input list of size n once, taking O(n) time. However, this does not contribute to the query complexity. For each query, where 'k' is the number of occurrences of the target number and 'm' is the number of queries, we perform a binary search on the precomputed list of positions to find the closest element. Binary search on a list of size 'k' takes O(log k) time. Therefore, for 'm' queries, the overall time complexity is O(m log k), assuming k is less than or equal to n.

Space Complexity

O(N) – The solution's primary space complexity comes from storing the positions of each number in the original list. In the worst-case scenario, where the original list contains N identical numbers, we would store N positions in our auxiliary data structure (e.g., a dictionary or a list of lists). Therefore, the space used grows linearly with the input size N. This precomputed data structure for storing indices uses O(N) auxiliary space.

Edge Cases

Case	How to Handle
nums is null or empty	Return an empty list immediately since there are no elements to query.
queries is null or empty	Return an empty list immediately since there are no queries to process.
nums contains only one element	Return [-1] for all queries since there can be no other equal element.
left index is out of bounds (negative or >= nums.length)	Return -1 for that specific query, or throw an exception to indicate an invalid query.
right index is out of bounds (negative or >= nums.length)	Return -1 for that specific query, or throw an exception to indicate an invalid query.
left > right	Return -1 for that query, indicating an invalid range.
Large input array (nums.length is very large) with many queries	Optimize for time complexity, possibly using pre-computation or indexing.
All numbers in nums are identical and the range includes more than one element.	Return left + 1 if left + 1 <= right, otherwise return -1.