# Minimum Absolute Difference Queries
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-absolute-difference-queries)
Canonical: https://scaleengineer.com/dsa/problems/minimum-absolute-difference-queries
**Data structures:** Array, Hash Table
---
## Problem
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
## Optimized Brute-Force per Query
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Prefix Counts
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int[] minDifference(int[] nums, int[][] queries) {
        int n = nums.length;
        int[][] prefixCounts = new int[n + 1][101];

        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= 100; j++) {
                prefixCounts[i + 1][j] = prefixCounts[i][j];
            }
            prefixCounts[i + 1][nums[i]]++;
        }

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0];
            int r = queries[i][1];

            int minDiff = Integer.MAX_VALUE;
            int lastPresent = -1;
            
            for (int k = 1; k <= 100; k++) {
                int count = prefixCounts[r + 1][k] - prefixCounts[l][k];
                if (count > 0) {
                    if (lastPresent != -1) {
                        minDiff = Math.min(minDiff, k - lastPresent);
                    }
                    lastPresent = k;
                }
            }

            if (minDiff == Integer.MAX_VALUE) {
                ans[i] = -1;
            } else {
                ans[i] = minDiff;
            }
        }
        return ans;
    }
}
```
### 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`.

# Solutions
### Java

```java
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 ; } }
```

### CPP

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

### Python

```python
class 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
```