Scale Engineer

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
ArrayHash 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] = [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 <= 105
  • 1 <= nums[i] <= 100
  • 1 <= queries.length <= 2 * 104
  • 0 <= li < ri < 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.

class Solution {    public int[] minDifference(int[] nums, int[][] queries) {        int[] ans = new int[queries.length];        for (int i = 0; i < queries.length; i++) {            int l = queries[i][0];            int r = queries[i][1];                        boolean[] isPresent = new boolean[101];            int uniqueCount = 0;            for (int j = l; j <= r; j++) {                if (!isPresent[nums[j]]) {                    isPresent[nums[j]] = true;                    uniqueCount++;                }            }                        if (uniqueCount < 2) {                ans[i] = -1;                continue;            }                        int minDiff = Integer.MAX_VALUE;            int lastPresent = -1;            for (int k = 1; k <= 100; k++) {                if (isPresent[k]) {                    if (lastPresent != -1) {                        minDiff = Math.min(minDiff, k - lastPresent);                    }                    lastPresent = k;                }            }            ans[i] = minDiff;        }        return ans;    }}

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.

Solutions

class 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 ; } }

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 →

Next problem