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 _anarray _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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8

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^5
  • 1 <= nums[i] <= 100
  • 1 <= queries.length <= 2 * 10^4
  • 0 <= li < ri < nums.length

Solution

Method 1 – Offline Query + Prefix Frequency + Sorted List

Intuition

For each query, we need to find the minimum absolute difference in a subarray. Since the range of values is small (1 ≤ nums[i] ≤ 10^5), we can use prefix frequency arrays and process queries offline. For each query, collect all unique values in the range, sort them, and compute the minimum difference between consecutive values.

Approach

  1. For each value in nums, build a prefix frequency array.
  2. For each query, collect all values that appear in the subarray using the prefix frequency.
  3. Sort the unique values and compute the minimum difference between consecutive values.
  4. If all values are the same, return -1 for that query.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<vector<int>> freq(n+1, vector<int>(100001));
        for (int i = 0; i < n; ++i) {
            freq[i+1] = freq[i];
            freq[i+1][nums[i]]++;
        }
        vector<int> ans;
        for (auto& q : queries) {
            int l = q[0], r = q[1]+1;
            vector<int> vals;
            for (int v = 1; v <= 100000; ++v) {
                if (freq[r][v] - freq[l][v] > 0) vals.push_back(v);
            }
            if (vals.size() < 2) ans.push_back(-1);
            else {
                int minDiff = INT_MAX;
                for (int i = 1; i < vals.size(); ++i)
                    minDiff = min(minDiff, vals[i] - vals[i-1]);
                ans.push_back(minDiff);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func minDifference(nums []int, queries [][]int) []int {
    n := len(nums)
    freq := make([][]int, n+1)
    for i := range freq {
        freq[i] = make([]int, 100001)
    }
    for i := 0; i < n; i++ {
        copy(freq[i+1], freq[i])
        freq[i+1][nums[i]]++
    }
    ans := make([]int, len(queries))
    for qi, q := range queries {
        l, r := q[0], q[1]+1
        vals := []int{}
        for v := 1; v <= 100000; v++ {
            if freq[r][v]-freq[l][v] > 0 {
                vals = append(vals, v)
            }
        }
        if len(vals) < 2 {
            ans[qi] = -1
        } else {
            minDiff := 1 << 30
            for i := 1; i < len(vals); i++ {
                if vals[i]-vals[i-1] < minDiff {
                    minDiff = vals[i]-vals[i-1]
                }
            }
            ans[qi] = minDiff
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int[] minDifference(int[] nums, int[][] queries) {
        int n = nums.length;
        int[][] freq = new int[n+1][100001];
        for (int i = 0; i < n; ++i) {
            System.arraycopy(freq[i], 0, freq[i+1], 0, 100001);
            freq[i+1][nums[i]]++;
        }
        int[] ans = new int[queries.length];
        for (int qi = 0; qi < queries.length; ++qi) {
            int l = queries[qi][0], r = queries[qi][1]+1;
            List<Integer> vals = new ArrayList<>();
            for (int v = 1; v <= 100000; ++v) {
                if (freq[r][v] - freq[l][v] > 0) vals.add(v);
            }
            if (vals.size() < 2) ans[qi] = -1;
            else {
                int minDiff = Integer.MAX_VALUE;
                for (int i = 1; i < vals.size(); ++i)
                    minDiff = Math.min(minDiff, vals.get(i) - vals.get(i-1));
                ans[qi] = minDiff;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    fun minDifference(nums: IntArray, queries: Array<IntArray>): IntArray {
        val n = nums.size
        val freq = Array(n+1) { IntArray(100001) }
        for (i in 0 until n) {
            for (v in 1..100000) freq[i+1][v] = freq[i][v]
            freq[i+1][nums[i]]++
        }
        val ans = IntArray(queries.size)
        for ((qi, q) in queries.withIndex()) {
            val (l, r) = q[0] to q[1]+1
            val vals = mutableListOf<Int>()
            for (v in 1..100000) {
                if (freq[r][v] - freq[l][v] > 0) vals.add(v)
            }
            if (vals.size < 2) ans[qi] = -1
            else {
                var minDiff = Int.MAX_VALUE
                for (i in 1 until vals.size)
                    minDiff = minOf(minDiff, vals[i] - vals[i-1])
                ans[qi] = minDiff
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def min_difference(nums: list[int], queries: list[list[int]]) -> list[int]:
    n = len(nums)
    freq = [[0]*100001 for _ in range(n+1)]
    for i in range(n):
        for v in range(1, 100001):
            freq[i+1][v] = freq[i][v]
        freq[i+1][nums[i]] += 1
    ans = []
    for l, r in queries:
        vals = [v for v in range(1, 100001) if freq[r+1][v] - freq[l][v] > 0]
        if len(vals) < 2:
            ans.append(-1)
        else:
            min_diff = min(vals[i] - vals[i-1] for i in range(1, len(vals)))
            ans.append(min_diff)
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

impl Solution {
    pub fn min_difference(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let n = nums.len();
        let mut freq = vec![vec![0; 100001]; n+1];
        for i in 0..n {
            for v in 1..=100000 {
                freq[i+1][v] = freq[i][v];
            }
            freq[i+1][nums[i] as usize] += 1;
        }
        let mut ans = vec![];
        for q in queries.iter() {
            let l = q[0] as usize;
            let r = q[1] as usize + 1;
            let mut vals = vec![];
            for v in 1..=100000 {
                if freq[r][v] - freq[l][v] > 0 {
                    vals.push(v as i32);
                }
            }
            if vals.len() < 2 {
                ans.push(-1);
            } else {
                let mut min_diff = i32::MAX;
                for i in 1..vals.len() {
                    min_diff = min_diff.min(vals[i] - vals[i-1]);
                }
                ans.push(min_diff);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    minDifference(nums: number[], queries: number[][]): number[] {
        const n = nums.length;
        const freq = Array.from({length: n+1}, () => Array(100001).fill(0));
        for (let i = 0; i < n; ++i) {
            for (let v = 1; v <= 100000; ++v) freq[i+1][v] = freq[i][v];
            freq[i+1][nums[i]]++;
        }
        const ans: number[] = [];
        for (const [l, r] of queries) {
            const vals: number[] = [];
            for (let v = 1; v <= 100000; ++v) {
                if (freq[r+1][v] - freq[l][v] > 0) vals.push(v);
            }
            if (vals.length < 2) ans.push(-1);
            else {
                let minDiff = Number.MAX_SAFE_INTEGER;
                for (let i = 1; i < vals.length; ++i)
                    minDiff = Math.min(minDiff, vals[i] - vals[i-1]);
                ans.push(minDiff);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(Q * V)
    • Q = number of queries, V = value range (up to 10^5).
  • 🧺 Space complexity: O(N * V)
    • For prefix frequency arrays.