Minimum Absolute Difference Queries
MediumUpdated: Aug 2, 2025
Practice on:
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 not0becausea[i]anda[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:
xifx >= 0.-xifx < 0.
Examples
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^51 <= nums[i] <= 1001 <= queries.length <= 2 * 10^40 <= 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
- For each value in nums, build a prefix frequency array.
- For each query, collect all values that appear in the subarray using the prefix frequency.
- Sort the unique values and compute the minimum difference between consecutive values.
- If all values are the same, return -1 for that query.
Code
C++
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;
}
};
Go
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
}
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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
}
}
TypeScript
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.