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.
[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] = [li, ri]. For each query i, compute the minimum absolute difference of the subarray nums[li...ri] containing the elements of nums between the 0-based indices li and ri (inclusive).
Return an array ans where ans[i] is the answer to the ith 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 <= 1051 <= nums[i] <= 1001 <= queries.length <= 2 * 1040 <= li < ri < nums.lengthThis approach involves extracting the subarray for each query, sorting it, and then finding the minimum absolute difference by checking adjacent elements.
Considering the constraints, this approach might not be optimal, but it is straightforward and leverages the fact that the minimum difference will be between consecutive elements in a sorted sequence.
The function processes each query by slicing the nums array and sorting the subarray. It then calculates the minimum difference between consecutive elements in the sorted subarray. If all elements in the subarray are the same, it returns -1. Otherwise, it returns the smallest difference.
Time Complexity: O(q * n * log(n)), where q is the number of queries and n is the average size of the subarray.
Space Complexity: O(n) due to the space needed to store the sorted subarray.
To efficiently compute the minimum absolute difference for each query, we can use a prefix frequency-like array to keep track of the frequency of each number from 0 to 100 in the current range of queries.
This approach reduces redundant computations by leveraging frequency arrays and iteratively building the solution.
This solution precomputes the prefix frequency of each number from 1 to the maximum number in nums for each position. For each query [l, r], it determines the numbers present in the subarray by subtracting the prefix frequency at position l from that at position r+1. This allows for quick determination of differences between the numbers in constant time.
Time Complexity: O(n + q * m), where n is the length of nums, q is the number of queries, and m is the number of unique numbers possible (fixed here to 100).
Space Complexity: O(n * m) for storing the prefix frequency array.
This approach involves sorting the subarray and then comparing adjacent elements to find the minimum absolute difference.
This C solution sorts each queried subarray and scans for the minimum absolute difference between adjacent unique elements, ensuring O((r-l) log (r-l)) time complexity for each query due to sorting.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) per query due to sorting.
Space Complexity: O(n) for the subarray.
This approach involves preprocessing frequency counts of elements and using the preprocessed data to quickly answer each query.
The C implementation leverages a frequency array, which counts occurrences of elements, and checks adjacent elements for minimum difference calculation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(100 * q) where q is the number of queries due to fixed range count.
Space Complexity: O(1) ignoring result storage, as we use a fixed-size array for frequency.
| Approach | Complexity |
|---|---|
| Brute Force with Sorting | Time Complexity: O(q * n * log(n)), where q is the number of queries and n is the average size of the subarray. |
| Optimized Approach with Precomputation | Time Complexity: O(n + q * m), where n is the length of nums, q is the number of queries, and m is the number of unique numbers possible (fixed here to 100). |
| Approach 1: Sort and Compare Adjacent Elements | Time Complexity: O(n log n) per query due to sorting. |
| Approach 2: Frequency and Preprocessing | Time Complexity: O(100 * q) where q is the number of queries due to fixed range count. |
Minimum Distance between BST Nodes - Leetcode 783 - Python • NeetCodeIO • 22,987 views views
Watch 9 more video solutions →Practice Minimum Absolute Difference Queries with our built-in code editor and test cases.
Practice on FleetCode