Minimum Absolute Difference Queries

Med

#1740Time: O(Q * (N + K)), where `Q` is the number of queries, `N` is the length of `nums`, and `K` is the value range (100). For each query, we iterate the subarray (up to `N` elements) and then the value range (`K` elements). This will be too slow for the given constraints and likely result in a Time Limit Exceeded error.Space: O(K) for the `isPresent` array used within each query processing loop, where K is the range of values (100).

Data structures

Array Hash Table

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach is to process each query independently. For each query [l, r], we can iterate through the subarray nums[l...r] and find the unique numbers present. Due to the small range of values in nums (1 to 100), we can do this efficiently by checking for the presence of each number in the range [1, 100] within the subarray.

Algorithm

Initialize an answer array ans.
For each query [l, r]:
- Create a boolean array isPresent of size 101, initialized to false.
- Iterate j from l to r and set isPresent[nums[j]] = true.
- Find the minimum difference from the isPresent array:
  - Initialize min_diff = Integer.MAX_VALUE and last_present = -1.
  - Iterate k from 1 to 100.
  - If isPresent[k] is true:
    - If last_present was set, update min_diff = Math.min(min_diff, k - last_present).
    - Update last_present = k.
- If min_diff is still Integer.MAX_VALUE (fewer than 2 unique numbers), the answer is -1. Otherwise, it's min_diff.
- Store the result in ans.
Return ans.

Walkthrough

This approach handles each query one by one without any global precomputation. For a given query [l, r], we need to find the minimum absolute difference among the unique elements in nums[l...r]. We can leverage the constraint 1 <= nums[i] <= 100. Instead of sorting the subarray (which could be long), we can determine which numbers from 1 to 100 exist in the subarray. We use a boolean array, isPresent of size 101. We iterate through nums[j] for j from l to r and mark isPresent[nums[j]] = true. After identifying all present numbers, we can find the minimum difference by iterating from 1 to 100. We keep track of the last number we saw (last_present) and compute the difference with the current number. If fewer than two unique numbers are found, the answer is -1.

1class Solution {2    public int[] minDifference(int[] nums, int[][] queries) {3        int[] ans = new int[queries.length];4        for (int i = 0; i < queries.length; i++) {5            int l = queries[i][0];6            int r = queries[i][1];7            8            boolean[] isPresent = new boolean[101];9            int uniqueCount = 0;10            for (int j = l; j <= r; j++) {11                if (!isPresent[nums[j]]) {12                    isPresent[nums[j]] = true;13                    uniqueCount++;14                }15            }16            17            if (uniqueCount < 2) {18                ans[i] = -1;19                continue;20            }21            22            int minDiff = Integer.MAX_VALUE;23            int lastPresent = -1;24            for (int k = 1; k <= 100; k++) {25                if (isPresent[k]) {26                    if (lastPresent != -1) {27                        minDiff = Math.min(minDiff, k - lastPresent);28                    }29                    lastPresent = k;30                }31            }32            ans[i] = minDiff;33        }34        return ans;35    }36}

Complexity

Time

O(Q * (N + K)), where `Q` is the number of queries, `N` is the length of `nums`, and `K` is the value range (100). For each query, we iterate the subarray (up to `N` elements) and then the value range (`K` elements). This will be too slow for the given constraints and likely result in a Time Limit Exceeded error.

Space

O(K) for the `isPresent` array used within each query processing loop, where K is the range of values (100).

Trade-offs

Pros

Simple logic, doesn't require complex data structures or precomputation.
Low memory usage.

Cons

Highly inefficient due to re-calculating presence for each query.
Will not pass the time limits for the given constraints.

To optimize for multiple queries, we can precompute information about the nums array. By creating a prefix count for each number from 1 to 100, we can determine which numbers exist in any subarray [l, r] in O(K) time, where K is the value range. This makes query processing much faster.

Algorithm

Define K = 101 for the value range.
Create a prefix counts table prefixCounts of size (nums.length + 1) x K.
Populate the prefixCounts table:
- Iterate i from 1 to nums.length.
- For j from 1 to K-1, set prefixCounts[i][j] = prefixCounts[i-1][j].
- Increment the count for the current number: prefixCounts[i][nums[i-1]]++.
Initialize an answer array ans.
For each query [l, r]:
- Initialize min_diff = Integer.MAX_VALUE and last_present = -1.
- Iterate k from 1 to K-1:
  - Calculate the count of k in nums[l...r]: count = prefixCounts[r+1][k] - prefixCounts[l][k].
  - If count > 0:
    - If last_present != -1, update min_diff = Math.min(min_diff, k - last_present).
    - Set last_present = k.
- If min_diff is Integer.MAX_VALUE, set the answer to -1. Otherwise, set it to min_diff.
- Store the result in ans.
Return ans.

Walkthrough

The bottleneck in the brute-force approach is repeatedly scanning the subarray for each query. We can eliminate this by precomputing prefix counts. We'll use a 2D array, prefixCounts[i][j], to store the frequency of number j in the prefix of the nums array of length i (i.e., nums[0...i-1]). The size of this table will be (N+1) x (K+1), where N is nums.length and K is 100. We can build this table in O(N*K) time. For each index i from 1 to N, prefixCounts[i] is based on prefixCounts[i-1]. We copy the counts and increment the count for the number nums[i-1]. With this table, finding the count of a number j in a subarray nums[l...r] becomes an O(1) operation: prefixCounts[r+1][j] - prefixCounts[l][j]. For each query, we can now check for the presence of every number from 1 to 100 in O(K) total time. The rest of the logic is the same: iterate from 1 to 100, find consecutive present numbers, and calculate the minimum difference.

1class Solution {2    public int[] minDifference(int[] nums, int[][] queries) {3        int n = nums.length;4        int[][] prefixCounts = new int[n + 1][101];5 6        for (int i = 0; i < n; i++) {7            for (int j = 1; j <= 100; j++) {8                prefixCounts[i + 1][j] = prefixCounts[i][j];9            }10            prefixCounts[i + 1][nums[i]]++;11        }12 13        int[] ans = new int[queries.length];14        for (int i = 0; i < queries.length; i++) {15            int l = queries[i][0];16            int r = queries[i][1];17 18            int minDiff = Integer.MAX_VALUE;19            int lastPresent = -1;20            21            for (int k = 1; k <= 100; k++) {22                int count = prefixCounts[r + 1][k] - prefixCounts[l][k];23                if (count > 0) {24                    if (lastPresent != -1) {25                        minDiff = Math.min(minDiff, k - lastPresent);26                    }27                    lastPresent = k;28                }29            }30 31            if (minDiff == Integer.MAX_VALUE) {32                ans[i] = -1;33            } else {34                ans[i] = minDiff;35            }36        }37        return ans;38    }39}

Complexity

Time

O(N*K + Q*K), where `N` is `nums.length`, `Q` is `queries.length`, and `K` is the value range (100). `O(N*K)` is for the one-time precomputation, and `O(K)` is for each of the `Q` queries. This is efficient and passes within the time limits.

Space

O(N*K) to store the prefix counts table, where N is the length of `nums` and K is the value range (100). This is the main trade-off for the improved time complexity.

Trade-offs

Pros

Very efficient for a large number of queries after the initial setup cost.
Query time is independent of the subarray length.

Cons

Uses a significant amount of extra space for the prefix counts table.
The precomputation step can be slow if N or K are very large.

Solutions

Solution

1class Solution { public int [] minDifference ( int [] nums , int [][] queries ) { int m = nums . length , n = queries . length ; int [][] preSum = new int [ m + 1 ][ 101 ]; for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = 1 ; j <= 100 ; ++ j ) { int t = nums [ i - 1 ] == j ? 1 : 0 ; preSum [ i ][ j ] = preSum [ i - 1 ][ j ] + t ; } } int [] ans = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { int left = queries [ i ][ 0 ], right = queries [ i ][ 1 ] + 1 ; int t = Integer . MAX_VALUE ; int last = - 1 ; for ( int j = 1 ; j <= 100 ; ++ j ) { if ( preSum [ right ][ j ] > preSum [ left ][ j ]) { if ( last != - 1 ) { t = Math . min ( t , j - last ); } last = j ; } } if ( t == Integer . MAX_VALUE ) { t = - 1 ; } ans [ i ] = t ; } return ans ; } }

1class Solution { public: vector < int > minDifference ( vector < int >& nums , vector < vector < int >>& queries ) { int m = nums . size (), n = queries . size (); int preSum [ m + 1 ][ 101 ]; for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = 1 ; j <= 100 ; ++ j ) { int t = nums [ i - 1 ] == j ? 1 : 0 ; preSum [ i ][ j ] = preSum [ i - 1 ][ j ] + t ; } } vector < int > ans ( n ); for ( int i = 0 ; i < n ; ++ i ) { int left = queries [ i ][ 0 ], right = queries [ i ][ 1 ] + 1 ; int t = 101 ; int last = - 1 ; for ( int j = 1 ; j <= 100 ; ++ j ) { if ( preSum [ right ][ j ] > preSum [ left ][ j ]) { if ( last != - 1 ) { t = min ( t , j - last ); } last = j ; } } if ( t == 101 ) { t = - 1 ; } ans [ i ] = t ; } return ans ; } };

1class Solution : def minDifference ( self , nums : List [ int ], queries : List [ List [ int ]]) -> List [ int ]: m , n = len ( nums ), len ( queries ) pre_sum = [[ 0 ] * 101 for _ in range ( m + 1 )] for i in range ( 1 , m + 1 ): for j in range ( 1 , 101 ): t = 1 if nums [ i - 1 ] == j else 0 pre_sum [ i ][ j ] = pre_sum [ i - 1 ][ j ] + t ans = [] for i in range ( n ): left , right = queries [ i ][ 0 ], queries [ i ][ 1 ] + 1 t = inf last = - 1 for j in range ( 1 , 101 ): if pre_sum [ right ][ j ] - pre_sum [ left ][ j ] > 0 : if last != - 1 : t = min ( t , j - last ) last = j if t == inf : t = - 1 ans . append ( t ) return ans

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.

← Previous

Previous problem

Next problem