Minimum Absolute Difference Queries — Problem & Solution
Minimum Absolute Difference Queries solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Absolute Difference Queries is a medium coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Binary Search, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The minimum absolute difference of an array is the smallest |a[i] - a[j]| over pairs of indices with a[i] != a[j]. If every element is the same, it is -1.
You are given nums (every value between 1 and 100) and queries, where queries[i] = [l, r] names the subarray nums[l..r] (inclusive). Return an array whose i-th entry is the minimum absolute difference of that subarray.
Example 1
Input: nums = [5,5,2,9,9], queries = [[0,1],[0,2],[2,4],[3,4]]
Output: [-1,3,7,-1]
Explanation: `[5,5]` and `[9,9]` hold one distinct value each; `[5,5,2]` gives 3; `[2,9,9]` gives 7.
Example 2
Input: nums = [4,1,7,3], queries = [[0,3],[1,2]]
Output: [1,6]
Explanation: The whole array sorted is 1, 3, 4, 7 — the closest pair is 3 and 4.
Constraints
2 <= nums.length <= 10^51 <= nums[i] <= 1001 <= queries.length <= 2 * 10^40 <= l < r < nums.length
Hints for Minimum Absolute Difference Queries
Hint 1
Values live in 1..100, so a query only needs to know which of the 100 values occur in its range.
Hint 2
Once you know the present values in increasing order, the answer is the smallest gap between consecutive present values.
Hint 3
Keep, for each value, the sorted list of indices where it appears; a binary search tells whether any of them lies in
[l, r].
How to solve Minimum Absolute Difference Queries
With only 100 possible values, answer a query by walking the values in increasing order and asking, for each, whether it occurs inside [l, r]. Each value's occurrence positions are sorted, so that question is a single lower-bound search.
Approach
- For every value
vin 1..100, record the indices wherenums[i] == v(already in increasing order). - For a query
[l, r], setprev = -1,best = ∞, and loopvfrom 1 to 100. - Binary-search the first position of
vthat is>= l;vis present when such a position exists and is<= r. - When
vis present andprev != -1, updatebestwithv - prev; then setprev = v. - The query's answer is
best, or-1if it never changed (fewer than two distinct values).
Why it works
The minimum difference between distinct values in a multiset is always attained by two values that are adjacent in sorted order, so scanning the present values from small to large and taking consecutive gaps is exact. Presence of v in [l, r] is equivalent to its first position at or after l being at most r.
Complexity
- Time —
O(n + q · 100 · log n) - Space —
O(n)
Pitfalls
- Equal elements do not count — the difference must be between distinct values.
- A per-index prefix count table (n × 100) also works but uses 100× the memory.
- Queries are inclusive on both ends.
Reference solution
Python
from typing import List
import bisect
def minDifference(nums: List[int], queries: List[List[int]]) -> List[int]:
pos = [[] for _ in range(101)]
for i, v in enumerate(nums):
pos[v].append(i)
res = []
for l, r in queries:
prev = -1
best = 1000
for v in range(1, 101):
p = pos[v]
if not p:
continue
k = bisect.bisect_left(p, l)
if k < len(p) and p[k] <= r:
if prev != -1 and v - prev < best:
best = v - prev
prev = v
res.append(-1 if best == 1000 else best)
return resJava
public static int[] minDifference(int[] nums, int[][] queries) {
List<List<Integer>> pos = new ArrayList<>();
for (int v = 0; v <= 100; v++) pos.add(new ArrayList<>());
for (int i = 0; i < nums.length; i++) pos.get(nums[i]).add(i);
int[] res = new int[queries.length];
for (int q = 0; q < queries.length; q++) {
int l = queries[q][0], r = queries[q][1];
int prev = -1, best = 1000;
for (int v = 1; v <= 100; v++) {
List<Integer> p = pos.get(v);
if (p.isEmpty()) continue;
int lo = 0, hi = p.size();
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (p.get(mid) < l) lo = mid + 1; else hi = mid;
}
if (lo < p.size() && p.get(lo) <= r) {
if (prev != -1 && v - prev < best) best = v - prev;
prev = v;
}
}
res[q] = best == 1000 ? -1 : best;
}
return res;
}C++
vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
vector<vector<int>> pos(101);
for (int i = 0; i < (int)nums.size(); i++) pos[nums[i]].push_back(i);
vector<int> res;
for (auto& qr : queries) {
int l = qr[0], r = qr[1];
int prev = -1, best = 1000;
for (int v = 1; v <= 100; v++) {
const vector<int>& p = pos[v];
if (p.empty()) continue;
auto it = lower_bound(p.begin(), p.end(), l);
if (it != p.end() && *it <= r) {
if (prev != -1 && v - prev < best) best = v - prev;
prev = v;
}
}
res.push_back(best == 1000 ? -1 : best);
}
return res;
}JavaScript
var minDifference = function(nums, queries) {
var pos = [];
for (var v = 0; v <= 100; v++) pos.push([]);
for (var i = 0; i < nums.length; i++) pos[nums[i]].push(i);
var res = [];
for (var q = 0; q < queries.length; q++) {
var l = queries[q][0], r = queries[q][1];
var prev = -1, best = 1000;
for (var w = 1; w <= 100; w++) {
var p = pos[w];
if (p.length === 0) continue;
var lo = 0, hi = p.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (p[mid] < l) lo = mid + 1; else hi = mid;
}
if (lo < p.length && p[lo] <= r) {
if (prev !== -1 && w - prev < best) best = w - prev;
prev = w;
}
}
res.push(best === 1000 ? -1 : best);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets