Minimum Absolute Difference Queries solution and explanation
Google
7 more videos on this problem
Leetcode Solutions | 1906. Minimum Absolute Difference QueriesFraz · 24:24 · 6K views
LeetCode 1906. Minimum Absolute Difference QueriesHappy Coding · 21:09 · 1K views
Leetcode 1906 Minimum Absolute Difference QueriesSandip Jana · 12:51 · 872 views
1906. Minimum Absolute Difference Queries (Leetcode Medium)Programming Live with Larry · 7:46 · 664 views
【每日一题】1906. Minimum Absolute Difference Queries, 6/23/2021Huifeng Guan · 17:34 · 503 views
Leetcode Weekly Contest 246 | 1906. Minimum Absolute Difference Queries in EnglishCompetitive Somya · 6:16 · 482 views
LeetCode Weekly Contest 246 Question 4: Minimum Absolute Difference QueriesCoding Ninjas Webinars and Contest Editorials · 24:59 · 110 views
LeetCode 1906: Minimum Absolute Difference QueriesAlitaCode · 31:28 · 4 views
The 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 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:
xifx >= 0.-xifx < 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 <= 1051 <= nums[i] <= 1001 <= queries.length <= 2 * 1040 <= li < ri < nums.length
Approach overview
Problem Overview: You are given an integer nums and multiple queries [l, r]. For each query, consider the subarray nums[l..r] and return the minimum absolute difference between any two distinct values. If the subarray contains only one unique value, return -1. The challenge is answering many range queries efficiently.
Approach 1: Brute Force with Sorting (O(q * k log k) time, O(k) space)
For each query, extract the subarray nums[l..r], sort it, then compute the minimum difference between adjacent elements. Sorting works because the smallest absolute difference must appear between neighbors in sorted order. If the subarray length is k, sorting costs O(k log k) and scanning adjacent pairs costs O(k). This approach is straightforward but slow when there are many queries or large ranges.
Approach 2: Sort and Compare Adjacent Elements (O(q * k log k) time, O(k) space)
This method applies the same key observation: the minimum absolute difference must occur between adjacent elements after sorting. For each query, copy the range into a temporary array, sort it, then iterate once to compute the minimum gap. The algorithm is easy to implement in languages like C, C++, Java, Python, C#, and JavaScript. However, repeatedly sorting overlapping ranges leads to unnecessary work, making it inefficient for large datasets.
Approach 3: Frequency and Preprocessing (O(n * 100 + q * 100) time, O(n * 100) space)
The constraint that values lie between 1 and 100 enables a much faster approach. Build a prefix frequency table where prefix[i][v] stores how many times value v appears in the first i elements. For a query [l, r], determine which numbers exist in the range by subtracting prefix counts. Then scan values 1..100 and track the previous seen value to compute the minimum difference. Each query only checks 100 possible numbers, so it runs in constant time relative to input size.
This technique uses range counting and preprocessing, common in array query problems. The prefix table allows constant-time checks for whether a value exists in a range, avoiding repeated scans of the original array. A small fixed domain makes the algorithm extremely efficient.
Optimized Approach with Precomputation: The prefix-frequency strategy is the intended optimal solution. Precompute counts once, then process each query by iterating through the possible value range and calculating differences between consecutive present numbers. Time complexity becomes O(n * 100 + q * 100) and space complexity O(n * 100). This pattern appears frequently in range-query problems involving small integer domains and can be combined with structures like hash tables or prefix arrays.
Recommended for interviews: Start by explaining the sorting-based brute force to show the core observation about adjacent differences. Then transition to the prefix-frequency optimization. Interviewers expect the preprocessing solution because it reduces each query to scanning a fixed value range instead of repeatedly sorting subarrays.
Approach 1: Brute Force with Sorting
This approach involves extracting the subarray for each query, sorting it, and then finding the minimum absolute difference by checking adjacent elements.
Considering the constraints, this approach might not be optimal, but it is straightforward and leverages the fact that the minimum difference will be between consecutive elements in a sorted sequence.
def minAbsDifference(nums, queries):
results = []
for l, r in queries:
subarray = sorted(nums[l:r+1])
min_diff = float('inf')
for i in range(1, len(subarray)):
diff = subarray[i] - subarray[i-1]
if diff < min_diff:
min_diff = diff
results.append(min_diff if min_diff != float('inf') else -1)
return resultsThe function processes each query by slicing the nums array and sorting the subarray. It then calculates the minimum difference between consecutive elements in the sorted subarray. If all elements in the subarray are the same, it returns -1. Otherwise, it returns the smallest difference.
Time Complexity: O(q * n * log(n)), where q is the number of queries and n is the average size of the subarray.
Space Complexity: O(n) due to the space needed to store the sorted subarray.
Approach 2: Optimized Approach with Precomputation
To efficiently compute the minimum absolute difference for each query, we can use a prefix frequency-like array to keep track of the frequency of each number from 0 to 100 in the current range of queries.
This approach reduces redundant computations by leveraging frequency arrays and iteratively building the solution.
def minAbsDifferenceOptimized(nums, queries):
# Precompute prefix frequency of each element in nums
max_val = 100
n = len(nums)
m = len(queries)
prefix_freq = [[0] * (max_val + 1) for _ in range(n + 1)]
for i in range(n):
for num in range(1, max_val + 1):
prefix_freq[i + 1][num] = prefix_freq[i][num]
prefix_freq[i + 1][nums[i]] += 1
results = []
for l, r in queries:
min_diff = float('inf')
prev_num = -1
for num in range(1, max_val + 1):
if prefix_freq[r + 1][num] - prefix_freq[l][num] > 0:
if prev_num != -1:
min_diff = min(min_diff, num - prev_num)
prev_num = num
results.append(min_diff if min_diff != float('inf') else -1)
return resultsThis solution precomputes the prefix frequency of each number from 1 to the maximum number in nums for each position. For each query [l, r], it determines the numbers present in the subarray by subtracting the prefix frequency at position l from that at position r+1. This allows for quick determination of differences between the numbers in constant time.
Time Complexity: O(n + q * m), where n is the length of nums, q is the number of queries, and m is the number of unique numbers possible (fixed here to 100).
Space Complexity: O(n * m) for storing the prefix frequency array.
Approach 3: Approach 1: Sort and Compare Adjacent Elements
This approach involves sorting the subarray and then comparing adjacent elements to find the minimum absolute difference.
def minAbsDifference(nums, queries):
result = []
for l, r in queries:
subarray = sorted(nums[l:r+1])
min_diff = float('inf')
for i in range(1, len(subarray)):
if subarray[i] != subarray[i - 1]:
min_diff = min(min_diff, subarray[i] - subarray[i - 1])
result.append(-1 if min_diff == float('inf') else min_diff)
return resultimport java.util.*;
public class Solution {
public List<Integer> minAbsDifference(int[] nums, int[][] queries) {
List<Integer> result = new ArrayList<>();
for (int[] query : queries) {
int[] subarray = Arrays.copyOfRange(nums, query[0], query[1] + 1);
Arrays.sort(subarray);
int minDiff = Integer.MAX_VALUE;
for (int i = 1; i < subarray.length; i++) {
if (subarray[i] != subarray[i - 1]) {
minDiff = Math.min(minDiff, subarray[i] - subarray[i - 1]);
}
}
result.add(minDiff == Integer.MAX_VALUE ? -1 : minDiff);
}
return result;
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> minAbsDifference(vector<int>& nums, vector<vector<int>>& queries) {
vector<int> result;
for (auto &query : queries) {
vector<int> subarray(nums.begin() + query[0], nums.begin() + query[1] + 1);
sort(subarray.begin(), subarray.end());
int minDiff = INT_MAX;
for (int i = 1; i < subarray.size(); i++) {
if (subarray[i] != subarray[i - 1]) {
minDiff = min(minDiff, subarray[i] - subarray[i - 1]);
}
}
result.push_back(minDiff == INT_MAX ? -1 : minDiff);
}
return result;
}function minAbsDifference(nums, queries) {
const result = [];
for (const [l, r] of queries) {
const subarray = nums.slice(l, r + 1).sort((a, b) => a - b);
let minDiff = Number.MAX_VALUE;
for (let i = 1; i < subarray.length; i++) {
if (subarray[i] !== subarray[i - 1]) {
minDiff = Math.min(minDiff, subarray[i] - subarray[i - 1]);
}
}
result.push(minDiff === Number.MAX_VALUE ? -1 : minDiff);
}
return result;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int minAbsDifference(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
int* ans = (int*)malloc(queriesSize * sizeof(int));
*returnSize = queriesSize;
for (int q = 0; q < queriesSize; ++q) {
int left = queries[q][0];
int right = queries[q][1];
int subSize = right - left + 1;
int* subarray = (int*)malloc(subSize * sizeof(int));
for (int i = 0; i < subSize; ++i) {
subarray[i] = nums[left + i];
}
qsort(subarray, subSize, sizeof(int), compare);
int minDiff = INT_MAX;
for (int i = 1; i < subSize; ++i) {
if (subarray[i] != subarray[i - 1]) {
int diff = abs(subarray[i] - subarray[i - 1]);
if (diff < minDiff) {
minDiff = diff;
}
}
}
ans[q] = (minDiff == INT_MAX) ? -1 : minDiff;
free(subarray);
}
return ans;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> MinAbsDifference(int[] nums, int[][] queries) {
var result = new List<int>();
foreach (var query in queries) {
int l = query[0], r = query[1];
int[] subarray = new int[r - l + 1];
Array.Copy(nums, l, subarray, 0, r - l + 1);
Array.Sort(subarray);
int minDiff = int.MaxValue;
for (int i = 1; i < subarray.Length; i++) {
if (subarray[i] != subarray[i - 1]) {
minDiff = Math.Min(minDiff, subarray[i] - subarray[i - 1]);
}
}
result.Add(minDiff == int.MaxValue ? -1 : minDiff);
}
return result;
}
}In Python, this solution leverages the sorted function to operate on subarrays, then calculates the differences between adjacent distinct elements to determine the minimal difference.
Time Complexity: O(n log n) per query due to sorting.
Space Complexity: O(n) for subarray sorting.
Approach 4: Approach 2: Frequency and Preprocessing
This approach involves preprocessing frequency counts of elements and using the preprocessed data to quickly answer each query.
def minAbsDifference(nums, queries):
result = []
for l, r in queries:
freq = [0] * 101
for i in range(l, r + 1):
freq[nums[i]] += 1
prev = -1
min_diff = float('inf')
for i in range(101):
if freq[i] > 0:
if prev != -1:
min_diff = min(min_diff, i - prev)
prev = i
result.append(-1 if min_diff == float('inf') else min_diff)
return resultimport java.util.*;
public class Solution {
public List<Integer> minAbsDifference(int[] nums, int[][] queries) {
List<Integer> result = new ArrayList<>();
for (int[] q : queries) {
int[] freq = new int[101];
for (int i = q[0]; i <= q[1]; ++i) {
freq[nums[i]]++;
}
int prev = -1, minDiff = Integer.MAX_VALUE;
for (int i = 0; i <= 100; ++i) {
if (freq[i] > 0) {
if (prev != -1) {
minDiff = Math.min(minDiff, i - prev);
}
prev = i;
}
}
result.add(minDiff == Integer.MAX_VALUE ? -1 : minDiff);
}
return result;
}
}#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
vector<int> minAbsDifference(vector<int>& nums, vector<vector<int>>& queries) {
vector<int> result;
for (auto& q : queries) {
vector<int> freq(101, 0);
for (int i = q[0]; i <= q[1]; ++i) {
freq[nums[i]]++;
}
int prev = -1, minDiff = INT_MAX;
for (int i = 0; i <= 100; ++i) {
if (freq[i] > 0) {
if (prev != -1) {
minDiff = min(minDiff, i - prev);
}
prev = i;
}
}
result.push_back(minDiff == INT_MAX ? -1 : minDiff);
}
return result;
}function minAbsDifference(nums, queries) {
const result = [];
for (const [l, r] of queries) {
const freq = new Array(101).fill(0);
for (let i = l; i <= r; i++) {
freq[nums[i]]++;
}
let prev = -1;
let minDiff = Number.MAX_VALUE;
for (let i = 0; i <= 100; i++) {
if (freq[i] > 0) {
if (prev !== -1) {
minDiff = Math.min(minDiff, i - prev);
}
prev = i;
}
}
result.push(minDiff === Number.MAX_VALUE ? -1 : minDiff);
}
return result;
}#include <stdio.h>
#include <string.h>
#include <limits.h>
int minAbsDifference(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
int result[queriesSize];
*returnSize = queriesSize;
int freq[101];
for (int q = 0; q < queriesSize; ++q) {
memset(freq, 0, sizeof(freq));
int left = queries[q][0];
int right = queries[q][1];
for (int i = left; i <= right; ++i) {
freq[nums[i]]++;
}
int prev = -1, minDiff = INT_MAX;
for (int i = 0; i <= 100; ++i) {
if (freq[i] > 0) {
if (prev != -1) {
minDiff = (minDiff < i - prev) ? minDiff : i - prev;
}
prev = i;
}
}
result[q] = (minDiff == INT_MAX) ? -1 : minDiff;
}
int* ans = (int*)malloc(queriesSize * sizeof(int));
memcpy(ans, result, queriesSize * sizeof(int));
return ans;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> MinAbsDifference(int[] nums, int[][] queries) {
var result = new List<int>();
foreach (var query in queries) {
int[] freq = new int[101];
for (int i = query[0]; i <= query[1]; ++i) {
freq[nums[i]]++;
}
int prev = -1, minDiff = int.MaxValue;
for (int i = 0; i <= 100; i++) {
if (freq[i] > 0) {
if (prev != -1) {
minDiff = Math.Min(minDiff, i - prev);
}
prev = i;
}
}
result.Add(minDiff == int.MaxValue ? -1 : minDiff);
}
return result;
}
}This Python solution utilizes frequency counts to graph adjacent differences only between numbers present within subarrays.
Time Complexity: O(100 * q) due to iterating over a fixed frequency count.
Space Complexity: O(1), assuming space for query results is outside consideration.
Approach 5: Default Approach
function minDifference(nums: number[], queries: number[][]): number[] {
let m = nums.length,
n = queries.length;
let max = 100;
// let max = Math.max(...nums);
let pre: number[][] = [];
pre.push(new Array(max + 1).fill(0));
for (let i = 0; i < m; ++i) {
let num = nums[i];
pre.push(pre[i].slice());
pre[i + 1][num] += 1;
}
let ans = [];
for (let [left, right] of queries) {
let last = -1;
let min = Infinity;
for (let j = 1; j < max + 1; ++j) {
if (pre[left][j] < pre[right + 1][j]) {
if (last != -1) {
min = Math.min(min, j - last);
}
last = j;
}
}
ans.push(min == Infinity ? -1 : min);
}
return ans;
}func minDifference(nums []int, queries [][]int) []int {
m, n := len(nums), len(queries)
preSum := make([][101]int, m+1)
for i := 1; i <= m; i++ {
for j := 1; j <= 100; j++ {
t := 0
if nums[i-1] == j {
t = 1
}
preSum[i][j] = preSum[i-1][j] + t
}
}
ans := make([]int, n)
for i := 0; i < n; i++ {
left, right := queries[i][0], queries[i][1]+1
t, last := 101, -1
for j := 1; j <= 100; j++ {
if preSum[right][j]-preSum[left][j] > 0 {
if last != -1 {
if t > j-last {
t = j - last
}
}
last = j
}
}
if t == 101 {
t = -1
}
ans[i] = t
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with Sorting | Time Complexity: O(q * n * log(n)), where q is the number of queries and n is the average size of the subarray. |
| Optimized Approach with Precomputation | Time Complexity: O(n + q * m), where n is the length of nums, q is the number of queries, and m is the number of unique numbers possible (fixed here to 100). |
| Approach 1: Sort and Compare Adjacent Elements | Time Complexity: O(n log n) per query due to sorting. |
| Approach 2: Frequency and Preprocessing | Time Complexity: O(100 * q) due to iterating over a fixed frequency count. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Sorting | O(q * k log k) | O(k) | Small arrays or when the number of queries is very low |
| Sort and Compare Adjacent Elements | O(q * k log k) | O(k) | Simple implementation when optimization is not required |
| Frequency and Preprocessing (Prefix Counts) | O(n * 100 + q * 100) | O(n * 100) | Best choice when there are many queries and values are within a small fixed range |
Frequently asked questions
Is Minimum Absolute Difference Queries easy or hard?
Minimum Absolute Difference Queries is classified as a Medium problem on LeetCode. The brute force solution is simple, but identifying the prefix-frequency optimization using the limited value range requires stronger algorithmic insight.
Minimum Absolute Difference Queries Python/Java solution
Python and Java implementations typically build a prefix frequency matrix of size n x 101. For each query, compute the count of each value in the range and scan the values in ascending order to calculate the smallest difference between consecutive present numbers.
How to solve Minimum Absolute Difference Queries in O(n)?
Strict O(n) overall is not possible because multiple queries must be processed. The closest efficient solution preprocesses prefix frequencies in O(n * 100) time and answers each query in O(100). Since 100 is a fixed constant, the solution behaves nearly linear relative to input size.
What is the best approach for Minimum Absolute Difference Queries?
The optimal approach uses prefix frequency preprocessing. Since the values in nums are limited to the range 1 to 100, you can store cumulative counts for each value. For every query, check which numbers appear in the range and compute the minimum difference by scanning the value domain. This reduces each query to O(100) time after preprocessing.
Is Minimum Absolute Difference Queries asked at Google/Amazon/Meta?
Range query problems with preprocessing and prefix counting frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests your ability to exploit constraints such as small value ranges and design efficient query handling strategies.
What data structure is used in Minimum Absolute Difference Queries?
The optimal solution uses a prefix frequency array, which is essentially a 2D array storing cumulative counts of numbers from 1 to 100. The problem also involves core concepts from arrays and hash-based counting techniques for tracking value occurrences.
What is the time complexity of Minimum Absolute Difference Queries?
The brute force approach sorts each queried subarray and runs in O(q * k log k), where k is the subarray length. The optimized solution builds a prefix frequency table in O(n * 100) time and answers each query in O(100). Overall complexity becomes O(n * 100 + q * 100).