Minimum Absolute Difference Queries

Medium

Asked by:

3 views

Topics:

Arrays

The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.

For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different.

You are given an integer array nums and the array queries where queries[i] = [l_i, r_i]. For each query i, compute the minimum absolute difference of the subarray nums[l_i...r_i] containing the elements of nums between the 0-based indices l_i and r_i (inclusive).

Return an array ans where ans[i] is the answer to the i^th query.

A subarray is a contiguous sequence of elements in an array.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

Example 1:

Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
Output: [2,1,4,1]
Explanation: The queries are processed as follows:
- queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.
- queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.
- queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.
- queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.

Example 2:

Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
Output: [-1,1,1,3]
Explanation: The queries are processed as follows:
- queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the
  elements are the same.
- queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.
- queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.
- queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.

Constraints:

2 <= nums.length <= 10⁵
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 10⁴
0 <= l_i < r_i < nums.length

Try coding it in LeetCode

Minimum Absolute Difference Queries

Medium

Asked by:

3 views

Topics:

Arrays

The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.

For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different.

You are given an integer array nums and the array queries where queries[i] = [l_i, r_i]. For each query i, compute the minimum absolute difference of the subarray nums[l_i...r_i] containing the elements of nums between the 0-based indices l_i and r_i (inclusive).

Return an array ans where ans[i] is the answer to the i^th query.

A subarray is a contiguous sequence of elements in an array.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

Example 1:

Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
Output: [2,1,4,1]
Explanation: The queries are processed as follows:
- queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.
- queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.
- queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.
- queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.

Example 2:

Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
Output: [-1,1,1,3]
Explanation: The queries are processed as follows:
- queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the
  elements are the same.
- queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.
- queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.
- queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.

Constraints:

2 <= nums.length <= 10⁵
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 10⁴
0 <= l_i < r_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 input array `nums` and the number of queries?
Can the values in `nums` be negative, zero, or floating-point numbers?
If, for a given query range, all the numbers are the same, what should the function return?
Is the `queries` array guaranteed to be valid, meaning the left and right indices are always within the bounds of the `nums` array, and left <= right?
If no two distinct numbers exist within a given query range, what value should be returned?

Brute Force Solution

Approach

The goal is to find the smallest difference between any two numbers within a specified range of numbers. The brute force method involves looking at every possible pair of numbers within that range and calculating the difference between them.

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

For each query, focus on the section of numbers it specifies.
Within that section, take the first number and compare it to every other number in that section.
Calculate the difference between the first number and each of the other numbers.
Note down the smallest difference you found when comparing the first number to all the others. If all numbers are identical, note that there's no difference.
Now, repeat this process, starting with the second number and comparing it to every number after it in the section.
Keep repeating this process until you've compared every possible pair of numbers within the section.
After comparing every pair, look at all the smallest differences you noted down.
The smallest of those smallest differences is your answer for that query.

Code Implementation

def min_abs_difference_queries_brute_force(numbers, queries):
    results = []
    for query in queries:
        start_index = query[0]
        end_index = query[1]
        sub_array = numbers[start_index:end_index + 1]
        minimum_absolute_differences = []

        # Iterate through all possible pairs in the sub_array
        for first_index in range(len(sub_array)): 

            minimum_difference_for_element = float('inf')
            for second_index in range(first_index + 1, len(sub_array)): 
                difference = abs(sub_array[first_index] - sub_array[second_index])

                # Store the smallest difference seen so far
                minimum_difference_for_element = min(minimum_difference_for_element, difference) 

            #If min diff wasn't updated it's all identical numbers
            if minimum_difference_for_element == float('inf'): 
                minimum_difference_for_element = -1

            minimum_absolute_differences.append(minimum_difference_for_element)

        #Find the minimum difference across the whole sub array
        final_minimum_difference = float('inf')
        for difference in minimum_absolute_differences:

            # -1 values should be skipped
            if difference != -1:
                final_minimum_difference = min(final_minimum_difference, difference)

        # If the final result was not updated return -1
        if final_minimum_difference == float('inf'):
            results.append(-1)
        else:
            results.append(final_minimum_difference)

    return results

Big(O) Analysis

Time Complexity

O(n²) – For each query, we iterate through a subarray of size n (where n is the length of the subarray defined by the query). Within this subarray, we compare each element to every other element. The outer loop iterates n times, and the inner loop iterates a maximum of n-1 times (on average n/2). Therefore, the number of operations is proportional to n * (n/2), which simplifies to O(n²).

Space Complexity

O(1) – The provided plain English explanation describes an algorithm that iterates through sections of an input array and calculates differences between pairs of numbers. It keeps track of the smallest difference found so far for each pair comparison. The algorithm only requires storing a few variables: the current smallest difference, indices for iterating through the section, and potentially temporary variables for calculating the difference between each pair of numbers. The number of these variables does not depend on the input size N (where N is the size of the input array). Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The most efficient way to solve this involves precomputing information to quickly answer each question. We track where each number appears and then use that to drastically speed up finding the smallest differences.

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

First, create a way to remember the positions of each number in the original list. Think of it like making a directory that tells you exactly where to find each number.
When you get a question asking about a specific section of the list, use your directory to find all the numbers that appear in that section.
Sort the numbers you found in that section. This puts them in order from smallest to largest.
Now, go through the sorted numbers and find the smallest difference between any two numbers that are right next to each other. This is the minimum absolute difference for that question.
By pre-calculating and remembering number positions, each question becomes much faster to answer because you are only looking at the relevant parts of the original list.

Code Implementation

def min_difference_queries(numbers, queries):
    number_positions = {}
    for index, number in enumerate(numbers):
        if number not in number_positions:
            number_positions[number] = []
        number_positions[number].append(index)

    results = []
    for start_index, end_index in queries:
        numbers_in_range = []
        for number, positions in number_positions.items():
            for position in positions:
                if start_index <= position <= end_index:
                    numbers_in_range.append(number)
                    break

        # Sorting is crucial for finding the minimum adjacent difference.
        numbers_in_range.sort()

        if len(numbers_in_range) < 2:
            results.append(-1)
            continue

        minimum_difference = float('inf')
        for i in range(len(numbers_in_range) - 1):
            # Iterate through and compare differences.
            difference = abs(numbers_in_range[i] - numbers_in_range[i + 1])
            minimum_difference = min(minimum_difference, difference)

        # If no differences exist, return -1.
        results.append(minimum_difference)

    return results

Big(O) Analysis

Time Complexity

O(q * (r - l + log(r - l))) – Creating the initial index map takes O(n) time which is dominated by the query processing. For each of the q queries, we iterate through all numbers 1-100 (can be considered constant). For each number, we search for its occurrences within the range [l, r]. Extracting relevant indices takes O(1) (due to the index map). After finding the relevant numbers in the range, sorting them takes O((r - l) * log(r - l)) time, where (r - l) is the number of elements in the sub-array. Finally, finding the minimum absolute difference requires iterating through the sorted subarray once, which is O(r - l). Thus each query will take O((r - l) * log(r - l)), leading to a total of O(q * (r - l + (r-l)log(r-l))). Since (r-l) is always less than n, O(q * (r - l + log(r - l))) is a tighter bound.

Space Complexity

O(N) – The primary space usage stems from storing the positions of each number in the original list. This "directory," as described, will, in the worst case, need to store an entry for each number in the input list, where N is the length of the input list. Therefore, this position-tracking structure uses space proportional to N. The sorting step, depending on the algorithm used, could take at most O(N) space. Thus, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty nums array	Return an empty result list as no absolute differences can be computed.
nums array with only one element	Return an empty result list because calculating the absolute difference requires at least two elements.
Empty queries array	Return an empty result list because there are no queries to process.
Large nums array and numerous queries	Consider efficient precomputation techniques like prefix sums or sorted lists to optimize query processing time.
Queries where left > right	Handle such invalid queries, possibly by swapping 'left' and 'right' or returning a special error value.
nums array contains duplicate values	The solution should correctly handle duplicates without incorrectly reporting smaller differences.
nums array contains large integers (close to maximum integer value)	Be wary of potential integer overflow when calculating the absolute difference, and consider using larger data types (e.g., long) if necessary.
All values in the sub array are same	The minimum absolute difference would be zero, and the solution should correctly return 0.